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.