Fast Reachability Using DAG Decomposition
2023
Online
Elektronische Ressource
We present a fast and practical algorithm to compute the transitive closure (TC) of a directed graph. It is based on computing a reachability indexing scheme of a directed acyclic graph (DAG), G = (V, E). Given any path/chain decomposition of G we show how to compute in parameterized linear time such a reachability scheme that can answer reachability queries in constant time. The experimental results reveal that our method is significantly faster in practice than the theoretical bounds imply, indicating that path/chain decomposition algorithms can be applied to obtain fast and practical solutions to the transitive closure (TC) problem. Furthermore, we show that the number of non-transitive edges of a DAG G is ? width*|V| and that we can find a substantially large subset of the transitive edges of G in linear time using a path/chain decomposition. Our extensive experimental results show the interplay between these concepts in various models of DAGs.
Titel: |
Fast Reachability Using DAG Decomposition
|
---|---|
Link: | |
Veröffentlichung: | 2023 |
Medientyp: | Elektronische Ressource |
DOI: | 10.4230.LIPIcs.SEA.2023.2 |
Schlagwort: |
|
Sonstiges: |
|