License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.28
URN: urn:nbn:de:0030-drops-63797
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6379/
Chatterjee, Krishnendu ;
Rasmus Ibsen-Jensen, Rasmus ;
Pavlogiannis, Andreas
Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs
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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6379},
URN = {urn:nbn:de:0030-drops-63797},
doi = {10.4230/LIPIcs.ESA.2016.28},
annote = {Keywords: Graph algorithms, Constant-treewidth graphs, Reachability queries, Distance queries}
}
Keywords: |
|
Graph algorithms, Constant-treewidth graphs, Reachability queries, Distance queries |
Collection: |
|
24th Annual European Symposium on Algorithms (ESA 2016) |
Issue Date: |
|
2016 |
Date of publication: |
|
18.08.2016 |