Linear-time algorithm for the matched-domination problem in cographs

DOI10.1080/00207160.2010.539681zbMath1232.05166arXiv0902.1121OpenAlexW2170476137MaRDI QIDQ3101607

Chih-Chia Yao, Ruo-Wei Hung

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

zbMATH Keywords

graph algorithmcographspaired-dominationconstrained vertex setmatched-domination

Mathematics Subject Classification ID

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