MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Parallel algorithms with optimal speedup for bounded treewidth

Bodlaender, H. L. and Hagerup, Torben

July 1995, 27 pages.

Status: available - back from printing

We describe the first parallel algorithm with optimal speedup for constructing minimum-width tree decompositions of graphs of bounded treewidth. On $n$-vertex input graphs, the algorithm works in $O((\log n)^2)$ time using $O(n)$ operations on the EREW PRAM. We also give faster parallel algorithms with optimal speedup for the problem of deciding whether the treewidth of an input graph is bounded by a given constant and for a variety of problems on graphs of bounded treewidth, including all decision problems expressible in monadic second-order logic. On $n$-vertex input graphs, the algorithms use $O(n)$ operations together with $O(\log n\Tlogstar n)$ time on the EREW PRAM, or $O(\log n)$ time on the CRCW PRAM.

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Bodlaender, H. L. and Hagerup, Torben},
  TITLE = {Parallel algorithms with optimal speedup for bounded treewidth},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-95-1-017},
  MONTH = {July},
  YEAR = {1995},
  ISSN = {0946-011X},