Parallel recognition and decomposition of two terminal series parallel graphs

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²n + logm) 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 polylogrithmic factor of optimal.