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.
No takes yet. Share an insight, caveat, or question.
Valdes et al. (1982) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: