1982/05/01 by Jacobo Valdes, Robert E. Tarjan, Eugene L. Lawler · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Graph Labeling and Dimension Problems #Isomorphism (crystallography) #Transitive closure #Series (stratigraphy) #Transitive relation #Digraph #Combinatorics #Vertex (graph theory) #Class (philosophy) #Mathematics #Computer science #Discrete mathematics #Algorithm #Artificial intelligence #Graph
paper · doi:10.1137/0211023
openalex publication_date 1982/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.