Title: The Recognition of Series Parallel Digraphs
Abstract: 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.
Publication Year: 1982
Publication Date: 1982-05-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 605
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot