Decremental dominators and low-high orders in directed acyclic graphs (Master thesis)

Γιάννης, Κωνσταντίνος

Graphs are mathematical objects that model many diverse natural or man-made systems. A graph G = (V;E) consists of a set of vertices V together with a set E of edges. Graphs play an important role in computer science because they can be used to represent essentially any pairwise relationship between objects. For example, graphs can model transportation networks, communication networks, social networks, electronic circuits etc. Graphs are useful not only in computer science but in many academic areas such as chemistry, physics, mathematics and biology. Designing e cient graph algorithms can be a very challenging task. In this thesis, we consider practical algorithms for maintaining the dominator tree and a low-high order of a directed acyclic graph (DAG) under edge deletions. Let G=(V, E, s) be a directed graph with a distinguished start vertex s. The dominator tree D of G is a tree rooted at s, such that a vertex v is an ancestor of a vertex w if and only if every path from s to w include v. The dominator tree is a central tool in program optimization and code generation, and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low high order of G is a preorder of D that certi es the correctness of D and has further applications in connectivity and path-determination problems. First, we provide a carefully engineered version of a recent algorithm [ICALP 2017] for maintaining the dominator tree of a directed acyclic graph through a sequence of edge deletions. Then, we show how how to extend this algorithm so that it also maintains a low-high order of the given DAG. Our algorithms, for both tasks, run in O(mn) total time and O(m+n) space, where n is the number of vertices and m is the number of edges before any deletions. These results trivially extend to the case of reducible graphs. We study the eciency of our algorithms in practice by conducting an extensive experimental study, using real-world graphs, taken from a variety of application areas, and articial graphs. The experimental results show that both algorithms perform very well in practice and are orders of magnitude faster than recomputing from scratch.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Subject classification: Graphs
Keywords: Graphs,DAGs
Appears in Collections:Διατριβές Μεταπτυχιακής Έρευνας (Masters)

Files in This Item:
File Description SizeFormat 
Μ.Ε. ΓΙΑΝΝΗΣ ΚΩΝΣΤΑΝΤΙΝΟΣ 2018.pdf2.48 MBAdobe PDFView/Open

 Please use this identifier to cite or link to this item:
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.