Paired domination on interval and circular-arc graphs
We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) O ( m + n ) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) O ( m ( m + n ) ) time.
05c69 05c85 68q25 68r10 68w05