PARALLEL ALGORITHMS WITH OPTIMAL SPEEDUP FOR BOUNDED TREEWIDTH

We describe the first parallel algorithm with optimal speedup for cons tructing minimum-width tree decompositions of graphs of bounded treewi dth. On n-vertex input graphs, the algorithm works in O((log n)(2)) ti me using O(n) operations on the EREW PRAM. We also give faster paralle l 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 d ecision problems expressible in monadic second-order logic. On n-verte x input graphs, the algorithms use O(n) operations together with O(log n logn) time on the EREW PRAM, or O(log n) time on the CRCW PRAM.