Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs

Chatterjee, K, Ibsen-Jensen, R and Pavlogiannis, A (2016) Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs. .

Text reachabilitytreewidth.pdf - Submitted version Download (780kB)

Abstract

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(n1-ϵ · α(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.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	06 Dec 2018 09:17
Last Modified:	19 Jan 2023 01:09
DOI:	10.4230/LIPIcs.ESA.2016.28
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3029580