Improved algorithms for reachability and shortest path on low tree-width graphs
IST Austria Technical Report
Chatterjee, Krishnendu
Ibsen-Jensen, Rasmus
Pavlogiannis, Andreas
ddc:000
We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold:
1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing).
2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries.
3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries.
Our algorithms improve all existing results, and use very simple data structures.
IST Austria
2014
info:eu-repo/semantics/other
doc-type:other
text
http://purl.org/coar/resource_type/c_1843
https://research-explorer.ista.ac.at/record/5419
https://research-explorer.ista.ac.at/download/5419/5548
Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs</i>. IST Austria; 2014. doi:<a href="https://doi.org/10.15479/AT:IST-2014-187-v1-1">10.15479/AT:IST-2014-187-v1-1</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.15479/AT:IST-2014-187-v1-1
info:eu-repo/semantics/altIdentifier/issn/2664-1690
info:eu-repo/semantics/openAccess