License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.27
URN: urn:nbn:de:0030-drops-76319
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7631/
Georgiadis, Loukas ;
Giannis, Konstantinos ;
Karanasiou, Aikaterini ;
Laura, Luigi
Incremental Low-High Orders of Directed Graphs and Applications
Abstract
A flow graph G = (V, E, s) is 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 all paths 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 d of D that certifies the correctness of D, and has further applications in connectivity and path-determination problems.
In this paper we consider how to maintain efficiently a low-high order of a flow graph incrementally under edge insertions. We present algorithms that run in O(mn) total time for a sequence of edge insertions in a flow graph with n vertices, where m is the total number of edges after all insertions. These immediately provide the first incremental certifying algorithms for maintaining the dominator tree in O(mn) total time, and also imply incremental algorithms for other problems. Hence, we provide a substantial improvement over the O(m^2) straightforward algorithms, which recompute the solution from scratch after each edge insertion. Furthermore, we provide efficient implementations of our algorithms and conduct an extensive experimental study on real-world graphs taken from a variety of application areas. The experimental results show that our algorithms perform very well in practice.
BibTeX - Entry
@InProceedings{georgiadis_et_al:LIPIcs:2017:7631,
author = {Loukas Georgiadis and Konstantinos Giannis and Aikaterini Karanasiou and Luigi Laura},
title = {{Incremental Low-High Orders of Directed Graphs and Applications}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {27:1--27:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7631},
URN = {urn:nbn:de:0030-drops-76319},
doi = {10.4230/LIPIcs.SEA.2017.27},
annote = {Keywords: connectivity, directed graphs, dominators, dynamic algorithms}
}
|
Keywords: |
|
connectivity, directed graphs, dominators, dynamic algorithms |
|
Collection: |
|
16th International Symposium on Experimental Algorithms (SEA 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.08.2017 |
