A linear-time certifying algorithm for recognizing generalized series-parallel graphs
DOI10.1016/j.dam.2022.10.005zbMath1504.05275OpenAlexW4308842795MaRDI QIDQ2104935
Yong Zhang, Hing-Fung Ting, Francis Y. L. Chin, Yung Hyang 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
graph algorithmear-decompositiondepth-first searchseries-parallel graphouterplanar graphcertificaterecognition algorithmcertifying algorithmforbidden structuregeneralized series-parallel graphcertificate authentication
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Certifying algorithms
- Certifying 3-edge-connectivity
- Improved algorithms for graph four-connectivity
- Depth-first search is inherently sequential
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- Parallel recognition of series-parallel graphs
- Topology of series-parallel networks
- An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs
- LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
- The Recognition of Series Parallel Digraphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- Efficient Planarity Testing
- Finding Triconnected Components by Local Replacement
- Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: A linear-time certifying algorithm for recognizing generalized series-parallel graphs
