Klasy wykresów, dla których można obliczyć średnicę w czasie liniowym

Przypomnijmy, średnica grafu oznacza długość najdłuższego najkrótszej ścieżce . Biorąc pod uwagę wykres, oczywisty algorytm obliczania rozwiązuje problem wszystkich par najkrótszej ścieżki (APSP) i zwraca długość najdłuższej znalezionej ścieżki. $G$ $G$ $\text{diam}(G)$

Wiadomo, że problem APSP można rozwiązać w optymalnym czasie dla kilku klas grafów. Dla grafów ogólnych istnieje podejście teoretyczne do grafu algebraicznego działające w czasie , gdzie jest granicą mnożenia macierzy. Jednak obliczenie średnicy najwyraźniej nie jest krytycznie powiązane z APSP, jak pokazuje Yuster . $O(n^2)$ $O(M(n) \log n)$ $M(n)$

Czy znane są niektóre nietrywialne klasy grafów, dla których można obliczyć średnicę jeszcze szybciej, powiedzmy w czasie liniowym?

Szczególnie interesują mnie wykresy akordowe i wszelkie podklasy wykresów akordowych, takie jak wykresy blokowe. Na przykład, myślę, że średnicę wykresu akordowego można obliczyć w czasie , jeśli jest jednoznacznie reprezentowane jako drzewo kliki. Taki wykres jest także znany jako ur-akord . $G$ $O(n+m)$ $G$

graph-theory graph-algorithms shortest-path

— Juho
źródło

Do obliczenia średnicy, po podaniu drzewa kliki, wykresy akordowe zachowują się (prawie) tak samo jak drzewa. Podobnie na wykresie interwałowym dominująca para (która występuje na dowolnych grafach wolnych od AT) koniecznie decyduje o średnicy.

— Yixin Cao

@YixinCao Ale ogólnie liczba odrębnych drzew kliki, które może mieć wykres akordowy, jest wykładnicza pod względem liczby wierzchołków. Ponadto nie sądzę, aby średnica była taka sama w każdym drzewie kliki. Myślę, że jest to problem, ale na wykresie ur-akordowym średnica kliki jest niejednoznaczna. Czy miałeś na myśli coś innego?

— Juho

k + 1

$k+1$

k

$k$

@YixinCao OK, teraz rozumiem lepiej. Mimo to (szybki) algorytm nadal nie jest dla mnie oczywisty. Jeśli masz dodatkowe informacje lub referencje, prosimy o kontakt!

— Juho

$v$ $v$

$\{\text{AT},\text{claw}\}$

$m = \Omega(n^2)$ $K_n$ $o(n^2)$ $O(m+n)$ $o(n^2)$

$(\text{rising sun}- K_2)$

_{(źródło: graphclasses.org )}

Feodor F. Dragan, Falk Nicolai i Andreas Brandstädt, porządki LexBFS i potęgi grafów , WG 1996, LNCS 1197, 166–180. doi: 10.1007 / 3-540-62559-3_15

$\log n$

Derek G. Corneil, Leksykograficzne Szerokość Pierwsze wyszukiwanie - ankieta , WG 2004, LNCS 3353, 1–19. doi: 10.1007 / 978-3-540-30559-0_1

— András Salamon
źródło

O (n + m)

$O(n+m)$

o (n^{2})

$o(n^2)$

Wspomniane wykresy blokowe w pytaniu są dziedziczne na odległość. Algorytm czasu liniowego do obliczania średnicy dla wykresów dziedzicznych odległości jest podany w [1] (patrz Twierdzenie 5).

[1] Dragan, Feodor F. Dominujące kliki na wykresach dziedzicznych odległości. Springer Berlin Heidelberg, 1994.

— Juho
źródło