R.-W. Hung, C.-H. Chiu, and C.-C. Yao (Taiwan)
graph algorithm; cograph; paired-domination; maximum matched-paired-domination; linear-time algorithm.
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 ⊆ V is a paired dominating set of G if every vertex in V − S is adjacent to at least a vertex in S and if the subgraph G[S] induced by S contains at least one perfect matching. The paired domination problem is to nd a paired-dominating set of G with minimum cardinality. In this paper, we will introduce a generalization of the paired-domination problem, namely, the maximum matched-paired-domination problem. We then present a linear-time algorithm to solve it in cographs.
Important Links:
Go Back
