when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-63797
URL:

; ;

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

 pdf-format:

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

### BibTeX - Entry

@InProceedings{chatterjee_et_al:LIPIcs:2016:6379,
author =	{Krishnendu Chatterjee and Rasmus Rasmus Ibsen-Jensen and Andreas Pavlogiannis},
title =	{{Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs}},
booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
pages =	{28:1--28:17},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-015-6},
ISSN =	{1868-8969},
year =	{2016},
volume =	{57},
editor =	{Piotr Sankowski and Christos Zaroliagis},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},