Gibt es einen Algorithmus zur effizienten Verwaltung der Verbindungsinformationen für eine DAG, wenn Einfügungen / Löschungen vorhanden sind?

Ist es bei einem gerichteten azyklischen Graphen möglich, die folgenden Operationen effizient zu unterstützen?$G(V,E)$

• : bestimmtob ein Pfad in$isConnected(G,a,b)$ vom Knoten a zum Knoten$G$$a$$b$
• : Fügt eine Kante von$link(G,a,b)$$a$ dem Graphen G nach $b$$G$
• : Entfernt die Kante von$unlink(G,a,b)$$a$ nach in $b$$G$
• : Fügt einen Eckpunkt zu G hinzu$add(G,a)$
• : Entfernt einen Scheitelpunkt von G$remove(G,a)$

Ein paar Anmerkungen:

• Wenn wir es nicht erlaubten , scheint es einfach zu sein, die Verbindungsinformationen unter Verwendung einer Datenstruktur mit disjunkten Sätzen zu pflegen.$unlink$
• Offensichtlich implementiert werden könnte unter VerwendungTiefen- oder Breitensuche, die naive zeigerbasierte Darstellung des Graphen verwendet. Dies ist jedoch ineffizient.$isConnected$

Ich hoffe auf eine amortisierte konstante oder logarithmische Zeit für alle drei Operationen. Ist das möglich?

Das von Ihnen beschriebene Problem ist die volldynamische Erreichbarkeit der DAG (auch als volldynamischer transitiver Abschluss bei DAGs bezeichnet). Es wird als vollständig dynamisch bezeichnet, da die Benutzer auch die Versionen untersuchen, bei denen nur Löschvorgänge möglich sind (dann wird es als inkrementelle Erreichbarkeit bezeichnet) und bei denen nur Einfügungen möglich sind (als inkrementelle Erreichbarkeit bezeichnet).

Es gibt einige Kompromisse zwischen der Aktualisierungszeit und der Abfragezeit. Sei die Anzahl der Kanten und n die Anzahl der Eckpunkte. Für DAGs gaben Demetrescu und Italiano (FOCS'00) eine randomisierte Datenstruktur an, die Aktualisierungen (Randeinfügungen oder -löschungen) in O-Zeit ( n 1,58 ) und Erreichbarkeitsabfragen in O-Zeit ( n 0,58 ) unterstützt (Knoteneinfügungen / -löschungen werden ebenfalls unterstützt) in O (1) -Zeit); Dieses Ergebnis wurde von Sankowski (FOCS'04) erweitert, um für allgemein gerichtete Graphen zu arbeiten. Auch für DAGs zeigte Roditty (SODA'03), dass Sie die transitive Verschlussmatrix in der Gesamtzeit O ( m n + I · n 2 + D beibehalten können$m$$n$$n^{1.58}$$n^{0.58}$$mn+I·n^2+D$ ) , wobei ist die Anzahl der Einfügungen, D die Anzahl der Löschungen und natürlich die Abfragezeit ist O ( 1 ).$I$$D$$1$

Für allgemein gerichtete Graphen sind die folgenden (Aktualisierungs-, Abfrage-) Zeiten bekannt: (O ( ), O (1)) (Demetrescu und Italiano FOCS'00 (amortisiert), Sankowski FOCS'04 (ungünstigster Fall)) ( O ( m $n^2$ ),O($m\sqrt{n}$ )) (Roditty, Zwick FOCS'02), (O (m+nlogn), O (n)) (Roditty, Zwick STOC'04), (O (n 1,58 ), O (n 0,58 )) und (O (n 1,495 ), O (n$O(\sqrt{n}$$m+n\log n$$n$$n^{1.58}$$n^{0.58}$$n^{1.495}$$n^{1.495}$ )) von Sankowski (FOCS'04).

Das Erhalten einer polylogarithmischen Abfragezeit, ohne die Aktualisierungszeit zu stark zu erhöhen, ist ein großes offenes Problem, selbst für DAGs.

Ich denke, die besten Ergebnisse werden bisher in "Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure" diskutiert . In diesem Artikel wird ein randomisierter Algorithmus mit einer Abfragezeit von und einer Abfragezeit von O ( n 1,58$O(n^{0.58})$$O(n^{1.58})$ Aktualisierungszeit von .

(Dies gilt nur für die erste Version Ihrer Frage, mit linkund unlinkaber ohne addund remove.)