Efficient parallel recognition of cographs

DOI10.1016/j.dam.2005.02.004zbMath1101.68108OpenAlexW2166708791MaRDI 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

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

Related Items (3)

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

This page was built for publication: Efficient parallel recognition of cographs