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

作     者：Hung, Ruo-Wei 

作者机构：Chaoyang Univ Technol Dept Comp Sci & Informat Engn Taichung 41349 Taiwan 

出 版 物：《INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL》 (Int. J. Innov. Comput. Inf. Control)

年 卷 期：2010年第6卷第11期

页      面：4957-4978页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Council  Taiwan [NSC98-2221-E-324-018] 

主　　题：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