DIMACS TR: 93-24
Weighted Independent Perfect Domination on Cocomparability Graphs
Authors: Gerard J. Chang, C. Pandu Rangan, and Satyan R. Coorg
Suppose G=(V,E) is a graph in which every vertex v in 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 the sum of c(v), where v runs over all vertices in V, 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.
Key words: independent perfect domination, cocomparability graph, interval
Paper available at:
DIMACS Home Page