---
res:
bibo_abstract:
- '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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Rasmus
foaf_name: Ibsen-Jensen, Rasmus
foaf_surname: Ibsen-Jensen
foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0003-4783-0389
- foaf_Person:
foaf_givenName: Andreas
foaf_name: Pavlogiannis, Andreas
foaf_surname: Pavlogiannis
foaf_workInfoHomepage: http://www.librecat.org/personId=49704004-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-8943-0722
bibo_doi: 10.15479/AT:IST-2014-314-v1-1
dct_date: 2014^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/2664-1690
dct_language: eng
dct_publisher: IST Austria@
dct_title: Optimal tree-decomposition balancing and reachability on low treewidth
graphs@
...