Skip to Main content Skip to Navigation
Conference papers

Dynamic Dominators and Low-High Orders in DAGs

Abstract : We consider practical algorithms for maintaining the dominator tree and a low-high order in directed acyclic graphs (DAGs) subject to dynamic operations. Let G 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 all paths from s to w in G 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 certifies the correctness of D, and has further applications in connectivity and path-determination problems. We first provide a practical and carefully engineered version of a recent algorithm [ICALP 2017] for maintaining the dominator tree of a DAG through a sequence of edge deletions. The algorithm runs in O(mn) total time and O(m) space, where n is the number of vertices and m is the number of edges before any deletion. In addition, we present a new algorithm that maintains a low-high order of a DAG under edge deletions within the same bounds. Both results extend to the case of reducible graphs (a class that includes DAGs). Furthermore, we present a fully dynamic algorithm for maintaining the dominator tree of a DAG under an intermixed sequence of edge insertions and deletions. Although it does not maintain the O(mn) worst-case bound of the decremental algorithm, our experiments highlight that the fully dynamic algorithm performs very well in practice. Finally, we study the practical efficiency of all our algorithms by conducting an extensive experimental study on real-world and synthetic graphs.
Document type :
Conference papers
Complete list of metadata

Cited literature [46 references]  Display  Hide  Download

https://hal.inria.fr/hal-02335021
Contributor : Marie-France Sagot <>
Submitted on : Monday, October 28, 2019 - 9:13:04 AM
Last modification on : Monday, October 28, 2019 - 10:20:35 AM
Long-term archiving on: : Wednesday, January 29, 2020 - 1:30:13 PM

File

LIPIcs-ESA-2019-50.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Loukas Georgiadis, Konstantinos Giannis, Giuseppe Italiano, Aikaterini Karanasiou, Luigi Laura. Dynamic Dominators and Low-High Orders in DAGs. European Symposium on Algorithms (ESA), 2019, Munich, Germany. ⟨10.4230/LIPIcs.ESA.2019.50⟩. ⟨hal-02335021⟩

Share

Metrics

Record views

44

Files downloads

147