A linear-time certifying algorithm for recognizing generalized series-parallel graphs

DOI10.1016/J.DAM.2022.10.005zbMATH Open1504.05275OpenAlexW4308842795MaRDI QIDQ2104935FDOQ2104935

Authors: Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang, Yung H. Tsin 

Publication date: 8 December 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.10.005

Recommendations

• Parallel recognition of series-parallel graphs
• Certifying 3-edge-connectivity
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• scientific article; zbMATH DE number 2079335
• Parallel algorithms for series parallel graphs

zbMATH Keywords

depth-first searchgraph algorithmouterplanar graphcertificaterecognition algorithmseries-parallel graphear-decompositioncertifying algorithmforbidden structuregeneralized series-parallel graphcertificate authentication

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cites Work

• Depth-First Search and Linear Graph Algorithms
• Improved algorithms for graph four-connectivity
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Efficient Planarity Testing
• Title not available (Why is that?)
• The Recognition of Series Parallel Digraphs
• Depth-first search is inherently sequential
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Topology of series-parallel networks
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• Certifying algorithms
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Parallel recognition of series-parallel graphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Certifying 3-edge-connectivity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding Triconnected Components by Local Replacement
• Title not available (Why is that?)
• An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs

Cited In (2)

• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Certifying induced subgraphs in large graphs

Uses Software

• LEDA

This page was built for publication: A linear-time certifying algorithm for recognizing generalized series-parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104935)