Efficient parallel recognition of cographs

DOI10.1016/j.dam.2005.02.004zbMath1101.68108MaRDI QIDQ2565857

Stavros D. Nikolopoulos, Leonidas Palios

Publication date: 28 September 2005

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

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

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W10: Parallel algorithms in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C17: Perfect graphs

Related Items

On parallel recognition of cographs, The Hamiltonian problem on distance-hereditary graphs, Linear-time algorithm for the matched-domination problem in cographs

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
• Parallel recognition of complement reducible graphs and cotree construction
• Complement reducible graphs
• On a class of posets and the corresponding comparability graphs
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• A fast parallel algorithm to recognize P4-sparse graphs
• A time-optimal solution for the path cover problem on cographs.
• An optimal parallel co-connectivity algorithm
• An optimal path cover algorithm for cographs
• Parallel Algorithm for Cograph Recognition with Applications
• Parallel algorithms for cographs and parity graphs with applications
• A Linear Recognition Algorithm for Cographs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Dacey Graphs
• Graph Classes: A Survey
• The Pathwidth and Treewidth of Cographs
• Graph-Theoretic Concepts in Computer Science