\input zb-basic
\input zb-ioport
\iteman{io-port 05982501}
\itemau{Hung, Ruo-Wei; Yao, Chih-Chia}
\itemti{Linear-time algorithm for the matched-domination problem in cographs.}
\itemso{Int. J. Comput. Math. 88, No. 10, 2042-2056 (2011).}
\itemab
Summary: 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 $S \subseteq V$ is a paired-dominating set of $G$ if every vertex not in $S$ is adjacent to a vertex in $S$ and if the subgraph induced by $S$ contains a perfect matching. The paired-domination problem is to find a paired-dominating set of $G$ with minimum cardinality. This paper introduces a generalization of the paired-domination problem, namely, the matched-domination problem, in which some constrained vertices are in paired-dominating sets as far as they can. Further, possible applications are also presented. We then present a linear-time constructive algorithm to solve the matched-domination problem in cographs.
\itemrv{~}
\itemcc{}
\itemut{graph algorithm; paired-domination; constrained vertex set; matched-domination; cographs}
\itemli{doi:10.1080/00207160.2010.539681}
\end