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

Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas (2016) Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs. In: ESA: European Symposium on Algorithms , August 22-26, 2016, Aarhus, DK.

[img] Text
LIPIcs-ESA-2016-28.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2017-777-v1+1]
Download (565Kb)
Official URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.28

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=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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Graph algorithms, constant-treewidth graphs, reachability queries, distance queries
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 006 Special computer methods
Research Group: Chatterjee Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 01 Mar 2017 08:43
Last Modified: 30 Aug 2017 14:39
URI: https://repository.ist.ac.at/id/eprint/777

Actions (login required)

View Item View Item