A Linear-Time Algorithm for the Maximum Matched-Paired-Domination Problem in Cographs

R.-W. Hung, C.-H. Chiu, and C.-C. Yao (Taiwan)


graph algorithm; cograph; paireddomination; maximum matchedpaireddomination; lineartime 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