WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS

Suppose G = (V, E) is a graph in which every vertex v is an element of 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 Sigma{c(v): v is an element of 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.