Linear-time algorithm for the matched-domination problem in cographs
From MaRDI portal
Publication:3101607
DOI10.1080/00207160.2010.539681zbMath1232.05166arXiv0902.1121OpenAlexW2170476137MaRDI QIDQ3101607
Publication date: 29 November 2011
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0902.1121
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- An O(\(n\)) time algorithm for maximum matching on cographs
- On the rank of a cograph
- Labelling algorithms for paired-domination problems in block and interval graphs
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Distance-hereditary graphs
- Complement reducible graphs
- Handsome proof-nets: Perfect matchings and cographs
- A time-optimal solution for the path cover problem on cographs.
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- A simple linear time algorithm for cograph recognition
- Paired-domination of trees
- Achromatic number is NP-complete for cographs and interval graphs
- The clique operator on cographs and serial graphs
- A faster parallel connectivity algorithm on cographs
- Paired domination on interval and circular-arc graphs
- Efficient parallel recognition of cographs
- A Linear Recognition Algorithm for Cographs
- Paired-domination in graphs
- The Pathwidth and Treewidth of Cographs
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
This page was built for publication: Linear-time algorithm for the matched-domination problem in cographs