Die zeitliche Komplexität des Findens des Durchmessers eines Diagramms

Question

Was ist die Zeitkomplexität, um den Durchmesser eines Diagramms zu finden $ g = (v, e) $?

• $ {O} (| v |^2) $
• $ {O} (| v |^2+| v | cdot | e |) $
• $ {O} (| v |^2 cdot | e |) $
• $ {O} (| v | cdot | e |^2) $

Der Durchmesser eines Diagramms $ g $ ist das Maximum der kürzesten Pfadentfernungen zwischen allen Eckpunktpaaren in einem Diagramm.

Ich habe keine Ahnung, was ich dagegen tun soll, ich brauche eine vollständige Analyse, wie man ein solches Problem lösen kann.

Answer 1

Aktualisieren:

Diese Lösung ist nicht korrekt.

Die Lösung ist leider nur wahr (und unkompliziert) für Bäume! Das Finden des Durchmessers eines Baumes braucht dies nicht einmal. Hier ist ein Gegenbeispiel für Diagramme (Durchmesser ist 4, der Algorithmus gibt 3 zurück, wenn Sie diesen $ v $ auswählen):

---

Wenn die Grafik gerichtet ist, ist dies ziemlich komplex, Hier ist etwas Papier Schnellere Ergebnisse im dichten Fall als die Verwendung von Algorithmen für alle kürzesten Wege.

Mein Hauptpunkt ist jedoch ungefähr der Fall, in dem sich die Grafik befindet nicht Regie und mit nicht negativen Weigeshs hörte ich mehrmals von einem schönen Trick:

1. Wählen Sie einen Scheitelpunkt $ v $
2. Finden Sie $ u $ so, dass $ D (v, u) $ maximal ist
3. Finden Sie $ w $ so, dass $ d (u, w) $ maximal ist
4. Return $ d (u, w) $

Seine Komplexität ist die gleiche wie zwei aufeinanderfolgende Breite.

Es schien Folklore zu sein, aber im Moment kämpfe ich immer noch darum, eine Referenz zu bekommen oder seine Korrektur beweisen. Ich werde aktualisieren, wenn ich eines dieser Ziele erreichen werde. Es scheint so einfach, dass ich meine Antwort jetzt poste, vielleicht wird es jemand schneller bekommen.

¹ Wenn die Grafik gewichtet ist, Wikipedia scheint $ o (| e |+| v | log | v |) $ zu sagen, aber ich bin mir nur sicher, dass $ o (| e | log | v |) $.

² Wenn das Diagramm nicht angeschlossen ist $ O (α (| v |)) $ So wählen Sie ein Element aus jeder angeschlossenen Komponente aus. Ich bin mir nicht sicher, ob dies notwendig ist und Sie können in diesem Fall den Durchmesser unendlich entscheiden.

Answer 2

Ich nehme an, du meinst das Durchmesser von $ g $ das ist der am längsten kürzeste Weg in $ g $.

Das Finden des Durchmessers kann durchgeführt werden, indem zuerst alle Paare kürzeste Pfade finden und die maximale Länge bestimmen. Floyd-Warshall-Algorithmus Tut dies in $ theta (| v |^3) $ time. Johnsons Algorithmus kann implementiert werden, um $ cal {o} (| v |^2 log | v | + | v | cdot | e |) $ time zu erreichen.

Eine kleinere Runtime-Grenze für die schlimmste Fälle scheint schwer zu erreichen, da $ cal {o} (| v |^2) $ Entfernungen zu berücksichtigen und zu berechnen, die in sublinearer (amortisierter) Zeit jederzeit schwierig sein wird; sehen hier für eine verwandte Grenze. Notiz Dies Papier, das einen anderen Ansatz verwendet und einen (leicht) schnelleren Algorithmus erhält.

Answer 3

Sie können auch einen theoretischen Ansatz von Algebraic Graph in Betracht ziehen. Der Durchmesser $ text {diom} (g) $ ist das geringste Ganzzahl $ t $ st der Matrix $ m = i+a $ hat die Eigenschaft, dass alle Einträge von $ m^t $ ungleich Null sind. Sie finden $ t $ von $ o ( log n) $ iterations der Matrixmultiplikation. Der Durchmesseralgorithmus erfordert dann $ O (m (n) log n) $ time, wobei $ m (n) $ die Grenze für die Matrixmultiplikation ist. Beispielsweise würde der Durchmesseralgorithmus beispielsweise mit der Verallgemeinerung des Coppersmith-Winograd-Algorithmus durch Vassilevska Williams in $ o (n^{2.3727} log n) $ ausgeführt. Eine kurze Einführung finden Sie in Kapitel 3 in Fan Chungs Buch hier.

Wenn Sie Ihre Aufmerksamkeit auf eine geeignete Grafikklasse beschränken, können Sie das APSP -Problem in optimaler Zeit $ O (n^2) lösen. Diese Klassen umfassen mindestens Intervalldiagramme, zirkuläre Bogendiagramme, Permutationsdiagramme, bipartitische Permutationsdiagramme, stark chordale Diagramme, Chordalbipartitengrafiken, distanzierte Hägchengrafiken und doppelte Chordkapsel. Zum Beispiel siehe Dragan, FF (2005). Schätzung aller Paare kürzeste Wege in eingeschränkten Graphfamilien: ein einheitlicher Ansatz. Journal of Algorithmen, 57 (1), 1-21 und die Referenzen darin.

Answer 4

Annahmen:
1. Die Grafik ist ungewichtet
2. Die Grafik ist gerichtet

O (| v || e |) Zeitkomplexität.

Algorithmus:

ComputeDiameter(G(V,E)):
  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

Erläuterung:
Wir suchen nach Zyklus. Wenn der Diagramm den Zyklus enthält, bewegen wir uns in der Schleife, sodass wir unendlich distanziert sind. Wir suchen nach verbundenem. Wenn das Diagramm nicht angeschlossen ist, bedeutet dies den Scheitelpunkt U von G1 zu Scheitelpunkt V in G2. Wobei G1 und G2 zwei Subgrafiken sind, die nicht verbunden sind. Also werden wir wieder unendlich distanziert sein. Wir werden BFS verwenden, um den maximalen Abstand zwischen einem bestimmten Knoten (U) an alle anderen Knoten (v) zu berechnen, die von u erreichbar sind. Dann werden wir maximal des zuvor berechneten Durchmessers und der Ergebnisrendite nach BFS einnehmen. Wir haben also einen Strom maximaler Durchmesser.

Laufzeitanalyse:

1. O (| e |) mit DFS
2. O (| e |) mit DFS
3. BFS läuft in O (| e |) Zeit.
4. Wir müssen die BFS -Funktion für jeden Scheitelpunkt aufrufen.

Gesamtzeit = o (| v || e |) + o (| e |) + o (| e |)
Da | v || e | > | E |
Wir haben also die Laufzeit als o (| v || e |).

BFS
DFS

Hinweis: Dies ist keine elegante Lösung für dieses Problem.