Ich weiß, dass Planaritätstest in O (v) durchgeführt werden kann (äquivalent zu O (e), seit planaren Graphen) habe O (v) Kanten) Zeit.
Ich frage mich, ob es online in O (1) amortisierten Zeit getan werden kann, wenn jede Kante hinzugefügt wird (immer noch O (e) Zeit insgesamt).
Mit anderen Worten, in einer Datenbanktabelle, die Kanten eines Graphen darstellt und einer Einschränkung unterliegt, dass der dargestellte Graph eben ist, wie viel Zeit muss das für die Verwaltung der Beschränkung verantwortliche DBMS nehmen, um jede vorgeschlagene Einfügung zu validieren? (Nehmen wir zur Vereinfachung an, dass es keine Löschungen gibt.) Muss er einen der O (v) -Planaritäts-Testalgorithmen erneut ausführen, um jede vorgeschlagene Insertion oder Gruppe von Insertionen zu testen?
Nach etwas mehr Forschung scheint es, dass die Antwort "ja" ist, es gibt Online-Algorithmen, aber "nein" gibt es keine mit O (1) amortisierter Laufzeit.
Hier ist eine Veröffentlichung von 1999 im Journal of the ACM, Vollständig dynamische Planaritätsprüfung mit Anwendungen , in dem die Autoren schrieben:
Insbesondere betrachten wir die folgenden drei Operationen auf einem planaren Graphen G: (i) Einfügen einer Kante, wenn der resultierende Graph planar bleibt; (ii) Löschen einer Kante; und (iii) testen, ob eine Kante zu dem Graph hinzugefügt werden könnte, ohne die Planarität zu verletzen. Wir zeigen, wie jede der obigen Operationen in O (n ^ 2/3) -Zeit unterstützt wird, wobei n die Anzahl der Scheitelpunkte im Graphen ist. Die Grenze für Tests und Löschungen ist Worst-Case, während die Grenze für Einfügungen amortisiert ist.
Ich fand auch die Zusammenfassung eines 1989 erschienenen Papiers Incremental Planarity Testing Ich beanspruche ein O (log n) für die Randeinfügung, aber ich bin mir nicht sicher, ob ihre Technik auch das Löschen abdeckt.
Die Veröffentlichung von 1999 bezieht sich auch auf einen O-Algorithmus (inverse-ackermann (total-operations, n)) für den Fall keiner Deletionen, der 1992 in einem Papier diskutiert wurde. psu.edu/viewdoc/download?doi=10.1.1.55.9410&rep=rep1&type=pdf"> Schneller inkrementeller Planaritätstest , aber CiteSeer ist im Moment nicht erreichbar, daher werde ich die Details später lesen .
Die Löschung ist nützlich für meine Bewerbung und ich habe Zugriff auf das J. ACM-Papier. Ich lese weiter die amortisierte O (n ^ 2/3) -Strategie.
Tags und Links algorithm graph-theory complexity-theory