2014/01/29 by Ching‐Chi Lin, Lin, Ching-Chi, Hai-Lun Tu +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1401.7594
openalex publication_date 2014/01/29 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
In a graph G, a vertex subset 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] contains a perfect matching. The paired-domination problem involves finding a smallest paired-dominating set of G. Given an intersection model of an interval graph G with sorted endpoints, Cheng et al. designed an O(m+n)-time algorithm for interval graphs and an O(m(m+n))-time algorithm for circular-arc graphs. In this paper, to solve the paired-domination problem in interval graphs, we propose an O(n)-time algorithm that searches for a minimum paired-dominating set of G incrementally in a greedy manner. Then, we extend the results to design an algorithm for circular-arc graphs that also runs in O(n) time.