SIAM Journal on Computing · 1998 · 127 citations · 40 references
Bounded TreewidthEngineeringMinimum-width Tree DecompositionsComputational ComplexityParallel MetaheuristicsParallel AlgorithmsParallel Complexity TheoryTree AutomatonDiscrete MathematicsParallel ComputingCombinatorial OptimizationTree LanguageComputer EngineeringComputer ScienceGraph AlgorithmCrcw PramGraph TheoryParallel ProcessingTime ComplexityParallel ProgrammingErew Pram
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 log*n) time on the EREW PRAM, or O(log n) time on the CRCW PRAM.
40