Parallel recognition and decomposition of two terminal series parallel graphs (Q1098313)

In this paper, we develop a parallel recognition and decomposition algorithm for two-terminal series parallel (TTSP) graphs. Given a directed acyclic graph G in edge list form, the algorithm determines whether G is a TTSP graph. If G is a TTSP graph, the algorithm constructs a decomposition tree for G. Some interesting properties of the TTSP graphs are derived in order to facilitate fast parallel processing. The algorithm runs in \(O(\log^ 2 n+\log m)\) time with \(O(n+m)\) processors on an exclusive read exclusive write PRAM where n (m) is the number of vertices (edges) in G. This algorithm is within a polylogarithmic factor of optimal.