A LINEAR-TIME ALGORITHM FOR THE RESTRICTED PAIRED-DOMINATION PROBLEM IN COGRAPHS

作者：Hung Ruo Wei^*

来源：International Journal of Innovative Computing Information and Control, 2010, 6(11): 4957-4978.

• Graph algorithms
• Linear-time algorithms
• Paired-domination
• Restricted paired-domination
• Cographs

Let G = (V, E) be a graph without isolated vertices A matching in G 2,5 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 subset of 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 restricted paired domination problem, where some vertices are restricted so as to be in paired dominating sets Further, possible applications are also presented We then present a linear-time constructive algorithm to solve the restricted paired domination problem in cographs

• 出版日期2010-11