Title: WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS
Authors: CHANG, GJ
RANGAN, CP
COORG, SR
應用數學系
Department of Applied Mathematics
Issue Date: 8-Dec-1995
Abstract: 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.
URI: http://hdl.handle.net/11536/1601
ISSN: 0166-218X
Journal: DISCRETE APPLIED MATHEMATICS
Volume: 63
Issue: 3
Begin Page: 215
End Page: 222
Appears in Collections:Articles


Files in This Item:

  1. A1995TJ93600002.pdf