93-24 Weighted Independent Perfect Domination on Cocomparability Graphs

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