Diagrammklassen, für die der Durchmesser in linearer Zeit berechnet werden kann

Denken Sie daran, dass der Durchmesser eines Graphen die Länge eines längsten kürzesten Pfades in G ist . Bei einem gegebenen Diagramm löst ein offensichtlicher Algorithmus zur Berechnung von diam ( G ) das Problem des kürzesten Pfades (APSP) für alle Paare und gibt die Länge des längsten gefundenen Pfades zurück.$G$$G$$\text{diam}(G)$

Es ist bekannt, dass das APSP-Problem für mehrere Graphklassen in optimaler -Zeit gelöst werden kann . Für allgemeine Graphen gibt es einen algebraischen graphentheoretischen Ansatz, der in der Zeit O ( M ( n ) log n ) ausgeführt wird, wobei M ( n ) die Grenze für die Matrixmultiplikation ist. Die Berechnung des Durchmessers ist jedoch offensichtlich nicht kritisch mit APSP verbunden, wie von Yuster gezeigt .$O(n^2)$$O(M(n) \log n)$$M(n)$

Sind einige nicht triviale Graphklassen bekannt, für die der Durchmesser noch schneller berechnet werden kann, beispielsweise in linearer Zeit?

Ich interessiere mich besonders für Akkordgraphen und alle Unterklassen von Akkordgraphen wie Blockgraphen. Ich denke zum Beispiel, dass der Durchmesser eines Akkordgraphen in O ( n + m ) berechnet werden kann , wenn G als Cliquenbaum eindeutig darstellbar ist. Ein solcher Graph wird auch als Ur-Akkord bezeichnet .$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)$

_{(Quelle: graphclasses.org )}

• Feodor F. Dragan, Falk Nicolai und Andreas Brandstädt, LexBFS-Ordnungen und Potenzen von Graphen , WG 1996, LNCS 1197, 166–180. doi: 10.1007 / 3-540-62559-3_15

$\log n$

• Derek G. Corneil, Lexikografische Breite Erste Suche - Eine Umfrage , WG 2004, LNCS 3353, 1–19. doi: 10.1007 / 978-3-540-30559-0_1

Die genannten Blockgraphen in der Frage sind entfernungserblich. Ein linearer Zeitalgorithmus zur Berechnung des Durchmessers für entfernungserbliche Graphen ist in [1] angegeben (siehe Satz 5).

[1] Dragan, Feodor F. Dominierende Cliquen in entfernungserblichen Graphen. Springer Berlin Heidelberg, 1994.