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

DOI10.1016/J.DAM.2022.10.005MaRDI QIDQ2104935zbMATH OpenOpenAlexFDO

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

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)

Recommendations

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

Cites work

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

Cited in

(2)

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

Describes a project that uses

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)