TY - GEN

T1 - Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs

AU - Chatterjee, Krishnendu

AU - Ibsen-Jensen, Rasmus Rasmus

AU - Pavlogiannis, Andreas

PY - 2016

Y1 - 2016

N2 - 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 = Θ(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 ϵ ∈ [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n
1-ϵ · α(n)) time, where α is the inverse of the Ackermann function, and at all times uses O(n
ϵ) space. The input graph G is not considered in the space complexity.

AB - 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 = Θ(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 ϵ ∈ [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n
1-ϵ · α(n)) time, where α is the inverse of the Ackermann function, and at all times uses O(n
ϵ) space. The input graph G is not considered in the space complexity.

KW - Constant-treewidth graphs

KW - Distance queries

KW - Graph algorithms

KW - Reachability queries

U2 - 10.4230/LIPIcs.ESA.2016.28

DO - 10.4230/LIPIcs.ESA.2016.28

M3 - Konferencebidrag i proceedings

SN - 978-3-95977-015-6

T3 - Leibniz International Proceedings in Informatics

SP - 28:1-28:17

BT - 24th Annual European Symposium on Algorithms (ESA 2016)

PB - Schloss Dagstuhl--Leibniz-Zentrum für Informatik

CY - Dagstuhl

ER -