標題: WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS
作者: CHANG, GJ
RANGAN, CP
COORG, SR
應用數學系
Department of Applied Mathematics
公開日期: 8-Dec-1995
摘要: 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
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 63
Issue: 3
起始頁: 215
結束頁: 222
Appears in Collections:Articles


Files in This Item:

  1. A1995TJ93600002.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.