Login
- Originaltitel:
- Algorithmic Methods for Lowest Common Ancestor Problems in Directed Acyclic Graphs
- Übersetzter Titel:
- Algorithmische Methoden für Lowest Common Ancestor Probleme in Gerichteten Azyklischen Graphen
- Autor:
- Nowak, Johannes
- Jahr:
- 2009
- Dokumenttyp:
- Dissertation
- Fakultät/School:
- Fakultät für Informatik
- Betreuer:
- Mayr, Ernst W. (Prof. Dr.)
- Gutachter:
- Esparza Estaun, Francisco Javier (Prof. Dr.)
- Sprache:
- en
- Fachgebiet:
- DAT Datenverarbeitung, Informatik
- Kurzfassung:
- Lowest common ancestor (LCA) problems in directed acyclic graphs
(dags) have attracted scientific interest in the recent years.
Directed acyclic graphs are powerful tools for modeling causality
systems or other kind of entity dependencies, and efficient solutions
to the respective lowest common ancestor problems are indispensable
computational tools with regard to proper analysis of these systems.
Similar problems in trees are widely understood, however, the
generalizations to dags fall short of achieving comparable
efficiencies.
In this work, we develop and analyze algorithmic techniques for solving LCA problems in dags. The main focus is on all-pairs LCA problems, i.e., problems that require the answers to the respective LCA queries for all vertex pairs in the dag. In particular, the basic problems studied are finding one arbitrary representative LCA for all vertex pairs and listing all LCAs for all vertex pairs. We identify and describe in-depth three basic algorithmic approaches that lead to efficient solutions to these problems, namely dynamic programming, matrix multiplication, and a path cover approach.
The dynamic programming method in combination with using transitive reduction yields algorithms that are efficient in the average case and -- as a result of an experimental study also described in this thesis -- in practice. However, the running times depend on the number of edges in the transitive reduction of the input dags and are hence vulnerable to special constructs such as dense bipartite graphs.
Matrix multiplication approaches lead to general upper time bounds for the two problems that improve upon hitherto best solutions. More specifically, we prove that representative LCAs for all vertex pairs can be computed in time O(n2.575), and all LCAs for all vertex pairs can be computed in time O(n3.334). We note in this place that any improvement of the matrix multiplication exponent automatically improves these bounds for the LCA problems.
The third algorithmic approach, a path cover technique, yields efficient solutions for the two problems in dags $G$ with small width w(G), namely O(n2 w(G) log n) for computing representative and O(n2 w(G)2 log2 n) for computing all LCAs. However, perhaps the most important result connected with the path cover technique is an improved algorithm for finding representative LCAs in general that restricts the class of dags for which the upper bound O(n2.575) is actually attained significantly. Further research in this direction might ultimately improve this bound.
Additionally, we review algorithmic applications of the presented techniques, namely problem variants in dynamic settings, in weighted dags, and under space-efficiency considerations. Although some of the upper time bounds that we present in this work might turn out to be tight, further study of these and alike problems seems to be a promising direction for future research.
Finally, we present the results of an experimental study of some of the algorithms described in this work, in particular, the algorithms that are based on dynamic programming. As a consequence, we conclude that both representative and all LCAs for all vertex pairs can be computed reasonably fast in practice, i.e., with runtime close to O(n2). - Übersetzte Kurzfassung:
- Die Berechnung von Lowest Common Ancestors (LCAs) in gerichteten
azyklischen Graphen (Dags) war in den vergangenen Jahren Gegenstand
zahlreicher wissenschaftlicher Arbeiten. Gerichtete azyklische Graphen
sind mächtige Werkzeuge zur Modellierung von
Kausalitätssystemen, und im Hinblick auf die Analyse solcher
Systeme sind effiziente Lösungen der betreffenden LCA-Probleme
unabdingbar. Ähnliche Probleme in Bäumen sind gut
verstanden, aber die Generalisierungen zu Dags erreichen noch keine
vergleichbare Effizienz.
In dieser Arbeit entwickeln und analysieren wir algorithmische Techniken zur Lösung von LCA-Problemen in Dags. Das Hauptaugenmerk liegt dabei auf sogenannten All-Pairs LCA-Problemen, d.h. Probleme, bei denen die Antworten für die betreffenden LCA-Anfragen für alle Knotenpaare in dem Dag berechnet werden. Die beiden grundlegenden betrachteten Probleme sind das Berechnen eines beliebigen (representative) LCAs und das Berechnen aller (all) LCAs für alle Knotenpaare. Wir identifizieren und beschreiben drei fundamentale algorithmische Ansätze, die zu effizienten Lösungen der Probleme führen, nämlich dynamisches Programmieren, Matrixmultiplikation und eine Technik, die auf Pfadabdeckungen basiert.
Dynamisches Programmieren in Verbindung mit transitiver Reduktion liefert Algorithmen, die im Average Case und -- als Ergebnis einer experimentellen Studie, die ebenfalls in dieser Arbeit vorgestellt wird -- in der Praxis effizient sind. Die Laufzeiten hängen jedoch von der Anzahl der Kanten in der transitiven Reduktion des Eingabedags ab, so dass dieser Ansatz für spezielle Graphkonstrukte, wie zum Beispiel dichten bipartiten Graphen, anfällig ist.
Die Verwendung von Matrixmultiplikation liefert allgemeine obere Zeitschranke für beide Probleme, die die bisher besten Lösungen verbessern. Im Speziellen können wir berweisen, dass representative LCAs für alle Knotenpaare in Zeit O(n2.575), und alle LCAs für alle Knotenpaare in Zeit O(n3.334) berechnet werden können. Desweitern führen Verbesserungen des Matrixmultiplikationsexponenten automatisch zur Verbesserung dieser Schranken.
Der dritte algorithmische Ansatz, der auf einer Pfadüberdeckung basiert, liefert effiziente Lösungen für Dags G mit geringer Weite w(G), nämlich O(n2 w(G) log n) für representative und O(n2 w(G)2 log2 n) für all LCAs. Das wichtigste Resultat im Zusammenhang mit dieser Technik ist aber ein verbesserter Algorithmus zur Berechnung der representative LCAs, der eine obere Zeitschranke von O(n2.575) hat, für den die Klasse der Eingabedags, für die diese Laufzeit auch tatsächlich benö tigt wird, aber signifikant eingeschränkt ist. Weitere Forschungen in diese Richtung könnten die Schranke letztendlich drücken.
Zusätzlich betrachten wir algorithmische Anwendungen der entwickelten Techniken, nämlich Problemvarianten in dynamischen Umgebungen, in gewichteten Dags und unter Berücksichtigung von Speichereffizienz. Obwohl einige der etablierten oberen Schranken scharf sein könnten, glauben wir, dass das weitere Studium solcher und ähnlicher Problemvarianten interessante Resultate verspricht.
Am Ende präsentieren wir die Ergebnisse einer experimentellen Studie der auf dynamischer Programmierung basierenden Algorithmen. Als Konsequenz dieser Studie folgern wir, dass sowohl representative als auch all LCAs in der Praxis mit zufriedenstellender Effizienz, nämlich mit Laufzeit von annähernd O(n2) berechnet werden können. - WWW:
- https://mediatum.ub.tum.de/?id=645701
- Eingereicht am:
- 04.02.2008
- Mündliche Prüfung:
- 06.11.2009
- Seiten:
- 122
- Urn (Zitierfähige URL):
- https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20080128-645701-1-8
- Letzte Änderung:
- 11.03.2010
BibTeX