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

DOI10.1080/00207160.2010.539681MaRDI QIDQ3101607zbMATH OpenOpenAlexFDO

Authors Ruo-Wei Hung, Chih-Chia Yao

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

cographsconstrained vertex setgraph algorithmmatched-dominationpaired-domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: Let $G=(V,E)$ be a graph without isolated vertices. A matching in $G$ is a set of independent edges in $G$. A perfect matching $M$ in $G$ is a matching such that every vertex of $G$ is incident to an edge of $M$. A set $SsubseteqV$ is a extit{paired-dominating set} of $G$ if every vertex in $V-S$ is adjacent to some vertex in $S$ and if the subgraph $G[S]$ induced by $S$ contains at least one perfect matching. The paired-domination problem is to find a paired-dominating set of $G$ with minimum cardinality. A set $MPDsubseteqE$ is a extit{matched-paired-dominating set} of $G$ if $MPD$ is a perfect matching of $G[S]$ induced by a paired-dominating set $S$ of $G$. Note that the paired-domination problem can be regard as finding a matched-paired-dominating set of $G$ with minimum cardinality. Let $mathcalR$ be a subset of $V$, $MPD$ be a matched-paired-dominating set of $G$, and let $V(MPD)$ denote the set of vertices being incident to edges of $MPD$. A extit{maximum matched-paired-dominating set} $MMPD$ of $G$ w.r.t. $mathcalR$ is a matched-paired-dominating set such that $|V(MMPD)capmathcalR|geqslant|V(MPD)capmathcalR|$. An edge in $MPD$ is called extit{free-paired-edge} if neither of its both vertices is in $mathcalR$. Given a graph $G$ and a subset $mathcalR$ of vertices of $G$, the extit{maximum matched-paired-domination problem} is to find a maximum matched-paired-dominating set of $G$ with the least free-paired-edges; note that, if $mathcalR$ is empty, the stated problem coincides with the classical paired-domination problem. In this paper, we present a linear-time algorithm to solve the maximum matched-paired-domination problem in cographs.

Recommendations

• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• A linear-time algorithm for paired-domination on circular-arc graphs
• Paired-domination of trees

Cites work

• A faster parallel connectivity algorithm on cographs
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• A Linear Recognition Algorithm for Cographs
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• A simple linear time algorithm for cograph recognition
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• A time-optimal solution for the path cover problem on cographs.
• Achromatic number is NP-complete for cographs and interval graphs
• An O(n) time algorithm for maximum matching on cographs
• Complement reducible graphs
• Distance-hereditary graphs
• Efficient parallel recognition of cographs
• Handsome proof-nets: Perfect matchings and cographs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Labelling algorithms for paired-domination problems in block and interval graphs
• On the rank of a cograph
• Paired domination on interval and circular-arc graphs
• Paired-domination in graphs
• Paired-domination of trees
• The clique operator on cographs and serial graphs
• The Pathwidth and Treewidth of Cographs

Cited in

(2)

• scientific article; zbMATH DE number 6531253 (Why is no real title available?)
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs

This page was built for publication: Linear-time algorithm for the matched-domination problem in cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3101607)