## DIMACS TR: 93-24

## Weighted Independent Perfect Domination on Cocomparability Graphs

### Authors: Gerard J. Chang, C. Pandu Rangan, and Satyan R. Coorg

**
ABSTRACT
**

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
graph

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-24.ps

DIMACS Home Page