A linear-time certifying algorithm for recognizing generalized series-parallel graphs
type: Item
instance of: scholarly article
title: A linear-time certifying algorithm for recognizing generalized series-parallel graphs
zbMATH Open document ID: 1504.05275
author: Francis Y. L. Chin
author: Hing-Fung Ting
author: Yong Zhang
author: Yung H. Tsin
published in: Discrete Applied Mathematics
publication date: 2022-12-08T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 7628645
zbMATH Keywords: graph algorithm
zbMATH Keywords: certifying algorithm
zbMATH Keywords: recognition algorithm
zbMATH Keywords: ear-decomposition
zbMATH Keywords: depth-first search
zbMATH Keywords: series-parallel graph
zbMATH Keywords: outerplanar graph
zbMATH Keywords: generalized series-parallel graph
zbMATH Keywords: forbidden structure
zbMATH Keywords: certificate
zbMATH Keywords: certificate authentication
describes a project that uses: LEDA
MaRDI profile type: Publication
full work available at URL: j.dam.2022.10.005
OpenAlex ID: W4308842795
cites work: Q4190666
cites work: LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
cites work: Topology of series-parallel networks
cites work: An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs
cites work: Parallel recognition of series-parallel graphs
cites work: Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
cites work: Finding Triconnected Components by Local Replacement
cites work: Q5572939
cites work: Q3785978
cites work: Efficient Planarity Testing
cites work: Improved algorithms for graph four-connectivity
cites work: Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
cites work: Certifying algorithms
cites work: Certifying 3-edge-connectivity
cites work: Linear algorithms to recognize outerplanar and maximal outerplanar graphs
cites work: Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
cites work: Depth-first search is inherently sequential
cites work: Q3886876
cites work: Linear-time computability of combinatorial problems on series-parallel graphs
cites work: Depth-First Search and Linear Graph Algorithms
cites work: The Recognition of Series Parallel Digraphs
cites work: Q3785974
cites work: Q3826618
DOI: 10.1016/J.DAM.2022.10.005
description: scientific article; zbMATH DE number 7628645