A new algorithm for the recognition of series parallel graphs
In this paper we develop a new linear-time algorithm for the recognition of series parallel graphs. The algorithm is based on a succinct representation of series parallel graphs for which the presence of an arc can be tested in constant time; space utilization is linear in the number of vertices. We show how to compute such a representation in linear time from a breadth-first spanning tree. Furthermore, we present a precise condition for the existence of such succinct representations in general, which is, for instance, satisfied by planar graphs.
|Department of Computer Science [CS]|
Schoenmakers, L.A.M. (1995). A new algorithm for the recognition of series parallel graphs. Department of Computer Science [CS]. CWI.