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

11

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.GGdiam(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(n2)O(M(n)logn)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 .GO(n+m)G

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+1k
@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

Odpowiedzi:

9

vv

{AT,claw}

m=Ω(n2)Kno(n2)O(m+n)o(n2)

(rising sunK2)

wykres wschodzącego słońca
(ź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

logn

  • 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(n2)