1995
A new algorithm for the recognition of series parallel graphs
Publication
Publication
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.
Additional Metadata | |
---|---|
CWI | |
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.
|