Author(s):

Chatterjee, Krishnendu; IbsenJensen, Rasmus; Pavlogiannis, Andreas

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

Title Series: 
LIPIcs

Affiliation 
IST Austria 
Abstract: 
We consider datastructures for answering reachability and distance queries on constanttreewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a datastructure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) singlesource 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 singlesource queries. The datastructure uses at all times O(n) space. Our second contribution is a spacetime tradeoff datastructure for distance queries. For any epsilon in [1/2,1], we provide a datastructure 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.

Keywords: 
Graph algorithms; Constanttreewidth graphs; reachability queries; distance queries

Conference Title:

ESA: European Symposium on Algorithms

Volume: 
57

Conference Dates:

August 2226, 2016

Conference Location:

Aarhus, DK

ISBN:

9783662483497

Publisher:

Springer

Date Published:

20160101

Start Page: 
Article number: 28

Copyright Statement: 
CC BY

Sponsor: 
The research was partly supported by Austrian Science Fund (FWF) Grant No P23499N23, FWF NFN Grant No S11407N23 (RiSE/SHiNE) and ERC Start grant (279307: Graph Games).

URL: 

DOI: 
10.4230/LIPIcs.ESA.2016.28

Open access: 
yes (OA journal) 