A linear-time algorithm for paired-domination on circular-arc graphs

作者：Lin Ching Chi^*; Tu Hai Lun

来源：Theoretical Computer Science, 2015, 591: 99-105.

DOI：10.1016/j.tcs.2015.05.002

• Paired-domination problem
• Perfect matching
• Interval graph
• Circular-arc graph

In a graph G, a vertex subset S subset of V (G) is said to be a dominating set of G if every vertex not in S is adjacent to a vertex in S. A dominating set S of a graph G is called a paired-dominating set if the induced subgraph G[S] contains a perfect matching. The paired-domination problem involves finding a minimum paired-dominating set of G. For this problem, Chen et al. [J. Comb. Optim. 19 (4) (2010) 457-470] proposed an O (n + m)-time algorithm on interval graphs and Cheng et al. [Discrete Appl. Math. 155 (16) (2007) 2077-2086] designed an O (m(n + m))-time algorithm on circular-arc graphs. In this paper, we strengthen the results of Cheng et al. by showing an O (n + m)-time algorithm. Moreover, the algorithm can be completed in O (n) time if an intersection model of a circular-arc graph G with sorted endpoints is given. Since interval graphs are circular-arc graphs, we also obtain a linear time algorithm on interval graphs.

• 出版日期2015-8-2