Weighted independent perfect domination on cocomparability graphs

Suppose G = (V, E) is a graph in which every vertex v ε{lunate} V is associated with a cost c(v). This paper studies the weighted independent perfect domination problem on G, i.e., the problem of finding a subset D of V such that every vertex in V is equal or adjacent to exactly one vertex in D and ∑c(v): v ε{lunate} D is minimum. We give an O(|V

E|) algorithm for the problem on cocomparability graphs. The algorithm can be implemented to run in O(|V|2.37) time. With some modifications, the algorithm yields an O(|V|+|E|) algorithm on interval graphs, which are special cocomparability graphs. © 1995.