Browsing by Author "RANGAN, CP"

Now showing 1 - 1 of 1

WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS
(1995-12-08)
CHANG, GJ
;
RANGAN, CP
;
COORG, SR
;
應用數學系
;
Department of Applied Mathematics
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(VE) 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.