Optimal tree-decomposition balancing and reachability on low treewidth graphs
IST Austria Technical Report
Chatterjee, Krishnendu
Ibsen-Jensen, Rasmus
Pavlogiannis, Andreas
ddc:000
We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries.
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/5427
https://research-explorer.ista.ac.at/download/5427/5471
Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Optimal Tree-Decomposition Balancing and Reachability on Low Treewidth Graphs</i>. IST Austria; 2014. doi:<a href="https://doi.org/10.15479/AT:IST-2014-314-v1-1">10.15479/AT:IST-2014-314-v1-1</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.15479/AT:IST-2014-314-v1-1
info:eu-repo/semantics/altIdentifier/issn/2664-1690
info:eu-repo/semantics/openAccess