The Recognition of Series Parallel Digraphs
- 1 May 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 11 (2), 298-313
- https://doi.org/10.1137/0211023
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.Keywords
This publication has 10 references indexed in Scilit:
- Efficient Computation of Expressions with Common SubexpressionsJournal of the ACM, 1980
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence ConstraintsPublished by Elsevier BV ,1978
- An Optimal Algorithm to Detect a Line Graph and Output Its Root GraphJournal of the ACM, 1974
- Testing for the Church-Rosser PropertyJournal of the ACM, 1974
- Tree-Manipulating Systems and Church-Rosser TheoremsJournal of the ACM, 1973
- The Transitive Reduction of a Directed GraphSIAM Journal on Computing, 1972
- Graphs Suppressible to an EdgeCanadian Mathematical Bulletin, 1972
- Topology of series-parallel networksJournal of Mathematical Analysis and Applications, 1965
- On graphs in which two vertices are distinguishedActa Mathematica Hungarica, 1964
- Some properties of line digraphsRendiconti del Circolo Matematico di Palermo Series 2, 1960