Gibt es einen Online-Algorithmus, um die Komponenten in einem sich ändernden ungerichteten Diagramm zu verfolgen?

12

Problem

Ich habe ein ungerichtetes Diagramm (mit mehreren Kanten), das sich mit der Zeit ändert. Knoten und Kanten können eingefügt und gelöscht werden. Bei jeder Änderung des Diagramms muss ich die verbundenen Komponenten dieses Diagramms aktualisieren.

Eigenschaften

Zusätzliche Eigenschaften sind, dass keine zwei Komponenten jemals wieder verbunden werden. Offensichtlich kann der Graph Zyklen bis zu einem beliebigen Betrag aufweisen (andernfalls wäre die Lösung trivial). Wenn eine Kante keinen Knoten , wird dieser Knoten niemals übernommen. Wenn jedoch , kann es in geändert werden .enn∈en∉e

Nähert sich

Bisher habe ich zwei mögliche Ansätze, aber wie Sie sehen werden, sind sie schrecklich:

Langsam zustandslos

Ich kann die Grafik jedes Mal ab den geänderten Elementen durchsuchen (dfs / bfs). Dies spart Platz, ist aber langsam, da wir für jede Modifikation O (n + m) haben.

Stateful schneller (-er) (?) Ansatz

Ich kann alle möglichen Pfade für jeden Knoten zu allen möglichen Knoten speichern, aber wenn ich es richtig sehe, wird dies O (n ^ 4) Speicher beanspruchen. Ich bin mir jedoch nicht sicher, wie die Laufzeitverbesserung ist (falls es überhaupt eine gibt, da ich die Informationen für jeden Knoten in derselben Komponente auf dem neuesten Stand halten muss).

Frage

Haben Sie Hinweise, wie ich mehr über dieses Problem erfahren kann, oder vielleicht einige Algorithmen, auf denen ich aufbauen kann?

Hinweis

Wenn es eine enorme Verbesserung der Laufzeit / des Speichers gibt, könnte ich mit einer nicht optimalen Lösung leben, die manchmal besagt, dass zwei Komponenten eine sind, aber ich würde natürlich eine optimale Lösung vorziehen.

ds.algorithms graph-theory approximation-algorithms online-algorithms Bitmaske
quelle
Wenn ich Ihre letzten beiden Sätze in "Eigenschaften" richtig lese, dann scheint es, dass Sie nur am dekrementellen Problem interessiert sind. In diesem Fall sollten Sie unbedingt die Arbeiten von Thorup zur inkrementellen dynamischen Konnektivität prüfen. (Sie finden das Zitat über die Zeiger von JeffE, die für die volldynamische Version des Problems stehen.)
Maverick Woo
@Maverick Woo: Es kann immer neue Kanten / Knoten geben. Ich denke, die letzte Eigenschaft ist aus genau diesem Grund nicht sehr stark. Gilt es immer noch als dekrementell?
Bitmaske
Hoppla, ich weiß nicht, wie ich den ersten Satz verpasst habe ... Siehe die "Antwort" unten.
Maverick Woo

Antworten:

16

Es gibt mehrere Datenstrukturen, die Kanteneinfügungen, Kantenlöschungen und Konnektivitätsabfragen (Befinden sich diese beiden Eckpunkte in derselben verbundenen Komponente?) In polylogarithmischer Zeit unterstützen.

Jeffε
quelle
Das klingt großartig, wenn ich erst einmal durch die Zeitungen bin, werde ich das höchstwahrscheinlich akzeptieren.
Bitmaske
6

Ich denke, Sie suchen nach dem sogenannten dynamischen Graph-Algorithmus für die Zerlegung verbundener Komponenten. Der Algorithmus von Holm, de Lichtenberg und Thorup [HLT01] hat die polylogarithmische Zeit bei jeder Kantenaktualisierung amortisiert. Es ist lange her, dass ich mich das letzte Mal mit dem Problem befasst habe, daher gibt es wahrscheinlich neuere Fortschritte.

[HLT01] Jacob Holm, Kristian de Lichtenberg und Mikkel Thorup. Polylogarithmisch deterministische volldynamische Algorithmen für Konnektivität, Minimum Spanning Tree, 2-Edge und Biconnectivity. Journal of the ACM , 48 (4): 723–760, Juli 2001. http://doi.acm.org/10.1145/502090.502095

Tsuyoshi Ito
quelle
Verhexen. Du schuldest mir eine Cola.
Jeffs
@ JeffE: Ich wusste nicht über dieses Spiel . Aber gemäß den Regeln habe ich das Spiel nicht verloren (ich bin nur im „verhext“ -Zustand), also schulde ich dir keine Cola, es sei denn, ich spreche weiter… oh, warte einen Moment.
Tsuyoshi Ito
Wenn Sie nur Reputationspunkte
eintauschen
5

(Lassen Sie mich vorerst nur bei den Konnektivitätsfragen bleiben, die für Ihre Anwendung leider nicht ausreichen.)

Viele der vorherigen Arbeiten zum dynamischen Konnektivitätsproblem beziehen sich auf das Kantenaktualisierungsmodell: Sie gehen davon aus, dass die Anzahl der Scheitelpunkte festgelegt ist, und Sie können Kanten einfügen und / oder löschen, während Sie Abfragen durchführen. Wenn Sie nur einfügen (löschen) können, ist dies inkrementell (dekrementell). Wenn Sie beides können, ist das voll dynamisch. Thorups Arbeiten, auf die JeffE (und ich im Kommentar) hingewiesen haben, sind allesamt für Edge-Updates gedacht.

AFAIK, die CS-Theorie-Community, fängt erst an, sich mit Vertex-Aktualisierungen für allgemeine Diagramme zu befassen. Es gab eine bahnbrechende Arbeit von Chan, Pătraşcu und Roditty in FOCS 2008. Unter diesem Link finden Sie eine kürzlich erschienene Überarbeitung (September 2010) und die darin enthaltenen Verweise.

Maverick Woo
quelle
Warum glauben Sie, dass Holm et. al. Ansatz funktioniert nicht für mein Problem? Ich würde es adoptieren.
Bitmaske
Wenn Ihr Diagramm einen begrenzten Grad aufweist, können Sie theoretisch eine Scheitelpunktaktualisierung mithilfe einer Reihe von Kantenaktualisierungen emulieren. Andernfalls kann ein einzelnes Vertex-Update (z. B. das Entfernen der Mitte eines Sterngraphen) die Konnektivität des Graphen drastisch verändern. In diesem Fall benötigen Sie das Ergebnis von Chan et al.
Maverick Woo
Aha. Ich hätte in der ursprünglichen Frage sagen sollen, dass Scheitelpunktentfernungen selten sind, also kann ich es mir leisten, dies Rand für Rand zu tun.
Bitmaske