2026-07-22T06:27:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18352 2024-03-06T11:01:34Z ddc:004 open_access

Fast Reachability Using DAG Decomposition Kritikakis, Giorgos Tollis, Ioannis G. graph algorithms hierarchy directed acyclic graphs (DAG) path/chain decomposition transitive closure transitive reduction reachability reachability indexing scheme 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giorgos Kritikakis and Ioannis G. Tollis 2023 Is Part Of LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2023.2 urn:nbn:de:0030-drops-183526 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.2 eng https://creativecommons.org/licenses/by/4.0/legalcode