The Recognition of Series Parallel Digraphs
Jacobo Valdes, Robert Endre Tarjan, Eugene L. Lawler · SIAM Journal on Computing · 1982
We present a linear-time algorithm to recognize the class of vertex series-parallel (VSP) digraphs. Our method is based on the relationship between VSP digraphs and the class of edge series-parallel multidigraphs. As a byproduct of our analysis, we obtain efficient methods to compute the transitive closure and transitive reduction of VSP digraphs, and to test isomorphism of minimal VSP digraphs.