2026-08-11T06:33:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6379 2024-03-06T10:38:06Z ddc:004 open_access

Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs Chatterjee, Krishnendu Rasmus Ibsen-Jensen, Rasmus Pavlogiannis, Andreas Graph algorithms Constant-treewidth graphs Reachability queries Distance queries We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-\epsilon} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Krishnendu Chatterjee and Rasmus Rasmus Ibsen-Jensen and Andreas Pavlogiannis 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.28 urn:nbn:de:0030-drops-63797 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.28 eng https://creativecommons.org/licenses/by/3.0/legalcode