Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
Maw‐Shang Chang · SIAM Journal on Computing · 1998
This paper first presents a unified approach to design efficient algorithms for the weighted domination problem and its three variants, i.e., the weighted independent, connected, and total domination problems, on interval graphs. Given an interval model with endpoints sorted, these algorithms run in time O(n) or O(n log log n) where n is the number of vertices. The results are then extended to solve the same problems on circular-arc graphs in O(n + m) time where m is the number of edges of the input graph.