Was ist der schnellste deterministische Algorithmus für die dynamische Erreichbarkeit von Digraphen ohne Randlöschung?

16

Was ist das beste deterministische Ergebnis, um den dynamischen transitiven Abschluss in einem gerichteten Graphen nur mit Kanteneinfügung beizubehalten?

Ich habe einige Artikel über das Problem des dynamischen transitiven Verschlusses sowohl beim Einfügen als auch beim Löschen von Kanten gelesen. Gibt es dafür jedoch bessere Algorithmen mit nur Kanteneinfügung?

ds.algorithms graph-theory graph-algorithms dynamic-algorithms Wei Wang
quelle
3
Wird dies nicht durch die Datenstruktur von union-find gelöst?
Tyson Williams
Ist Ihr Graph gerichtet oder ungerichtet? @TysonWilliams ist insofern korrekt, als Sie für ungerichtete Diagramme ohne Randlöschungen im Grunde nur eine Vereinigungssuche durchführen (jede Einfügung ist eine UNION-Operation)
Suresh Venkat
1
Ah .. Ich habe vergessen zu erwähnen, es ist Digraph. Mein schlechtes .... wird dann updaten.
Wei Wang

Antworten:

9

Eine alte Veröffentlichung von Italiano (GF Italiano. Amortisierte Effizienz einer Pfadabrufdatenstruktur. Theoretical Computer Science, 48 (2–3): 273–281, 1986.) gibt eine Datenstruktur an, die Kanteneinfügungen in amortisiert unterstützt Zeit- und Erreichbarkeitsabfragen in konstanter Zeit. Ich kenne keine besseren inkrementellen Algorithmen.Ö(n)

virgi
quelle