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

11

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

Juho
quelle
Für die Berechnung des Durchmessers verhalten sich Akkordgraphen nach Angabe des Cliquenbaums (fast) genauso wie Bäume. Ebenso entscheidet in einem Intervallgraphen notwendigerweise ein dominierendes Paar (das in allen AT-freien Graphen existiert) den Durchmesser.
Yixin Cao
@YixinCao Im Allgemeinen ist die Anzahl der unterschiedlichen Cliquenbäume, die ein Akkordgraph haben kann, exponentiell in der Anzahl der Eckpunkte. Außerdem glaube ich nicht, dass der Durchmesser in jedem Cliquenbaum gleich ist. Ich denke, das ist ein Problem, aber in einem Ur-Akkord-Diagramm ist der Durchmesser des Cliquenbaums eindeutig. Hattest du noch etwas anderes im Sinn?
Juho
k+1k
@ YixinCao OK, jetzt verstehe ich besser. Trotzdem ist ein (schneller) Algorithmus für mich immer noch nicht offensichtlich. Wenn Sie weitere Details oder Referenzen haben, wenden Sie sich bitte!
Juho

Antworten:

9

vv

{AT,claw}

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

(rising sunK2)

Grafik der aufgehenden Sonne
(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

logn

András Salamon
quelle
O(n+m)o(n2)