Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434044 | Theoretical Computer Science | 2015 | 7 Pages |
In a graph G , a vertex subset S⊆V(G)S⊆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]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)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))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)O(n+m)-time algorithm. Moreover, the algorithm can be completed in O(n)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.