Parallel algorithms for series parallel graphs and graphs with treewidth two (Q5943662): Difference between revisions

This paper improves on Eppstein's algorithm [see \textit{D. Eppstein}, Inf. Comput. 98, No. 1, 41-55 (1992; Zbl 0754.68056)] for recognising series-parallel graphs. The new algorithm uses \(O(\log m \log^{*} m)\) time and \(O(m)\) operations on an EREW PRAM, and \(O(\log m)\) time and \(O(m)\) operations on a CRCW PRAM to decide whether a given graph with \(m\) edges is series-parallel. If so, a decomposition tree can be built within the same resource bounds. A graph has treewidth at most two if and only if each of its blocks is a series-parallel graph. Consequently graphs of treewidth at most two can be recognised within these resource bounds, and tree decompositions of width two can be constructed as well. Hence efficient parallel algorithms can be found for a large number of problems on series-parallel graphs and graphs with treewidth bounded by two, including all problems that can be stated in monadic second-order logic.