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 G . Biorąc pod uwagę wykres, oczywisty algorytm obliczania diam ( G ) 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 O ( M ( n ) log n ) , gdzie M ( n ) 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 O ( n + m ) , jeśli G jest jednoznacznie reprezentowane jako drzewo kliki. Taki wykres jest także znany jako ur-akord .$G$$O(n+m)$$G$

$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

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.