Ph.D. thesis : Dynamic Connectivity in Graphs: Theory and Practice

David Alberts

Advisor: Prof. Dr. Emo Welzl

Die Dissertation beschäftigt sich mit theoretischen und praktischen Aspekten eines zentralen Problems im Gebiet der dynamischen Graphalgorithmen, dem Problem des dynamischen Zusammenhangs. Gegeben ist ein ungerichteter Graph mit fixer Knotenmenge. Gesucht ist eine Datenstruktur, die es erlaubt, Kanten einzufügen, Kanten zu löschen und Abfragen der Form ``Sind die Knoten a und b im aktuellen Graphen in derselben Zusammenhangskomponente?'' zu beantworten.

Auf der theoretischen Seite werden neben der aktuell besten Datenstruktur von Henzinger und King [6]auch die wichtigsten früheren Ansätze, Fredericksons Datenstruktur [5] sowie Sparsification [4], dargestellt. Außerdem beschreiben wir eine allgemeine Methode zur Analyse der durchschnittlichen Laufzeit eines dynamischen Graphalgorithmus bei zufälligen Eingaben. Unser Beitrag zur theoretischen Seite besteht in einer Verallgemeinerung der Sparsification-Technik auf Matroide und der Analysemethode für zufällige Eingaben. Letztere entstand in gemeinsamer Arbeit mit Monika R. Henzinger (s.a. [3]). Außerdem schlagen wir eine vereinfachte Variante des Algorithmus von Henzinger und King für zufällige Eingaben vor.

Auf der praktischen Seite wird eine bekannte Anwendung von dynamischem Zusammenhang in der statistischen Mechanik gezeigt, die Simulation von Phasenübergängen. Wir dokumentieren unsere Implementation des Algorithmus von Henzinger und King (s.a. [1]), und wir präsentieren eine experimentelle Studie mit Cattaneo und Italianos Sparsification-Implementation, unserer Implementation des Algorithmus von Henzinger und King, und zwei Implementationen einfacherer Lösungen des Problems (s.a. [2]).

Ein wichtiges Ergebnis des praktischen Teils ist der Nachweis der Realisierbarkeit und des praktischen Nutzens der Datenstruktur von Henzinger und King. Es sind mehrere tausend Operationen pro Sekunde auf Graphen mit mehreren Hundert Knoten auf einer SUN SparcStation 10 möglich. Außer bei dünn besetzten (weniger Kanten als Knoten) zufälligen Graphen, war unsere Implementation der Datenstruktur von Henzinger und King bzw. unsere Variante davon bei allen getesteten Eingabearten am schnellsten.

Referenzen

1. D. Alberts. Implementation of the dynamic connectivity algorithm by Monika Rauch Henzinger and Valerie King. TR B 95-10, Freie Universität Berlin, Inst. f. Informatik, 1995.
2. D. Alberts, G. Cattaneo, G. F. Italiano. An empirical study of dynamic graph algorithms. In Proc. 7th SODA, p. 192 - 201, 1996.
3. D. Alberts, M. R. Henzinger. Average case analysis of dynamic graph algorithms. In Proc. 6th  SODA, p. 312 - 321, 1995. (Technical Report)
4. D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. In Proc. 33rd FOCS, p. 60 - 69, 1992.
5. G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput., 14:781 - 798, 1985.
6. M. R. Henzinger, V. King. Randomized dynamic graph algorithms with polylogarithmic time per operartion. In Proc. 27th STOC, p. 519 - 527, 1995.