标题: | WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS |
作者: | CHANG, GJ RANGAN, CP COORG, SR 應用數學系 Department of Applied Mathematics |
公开日期: | 8-十二月-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 |
显示于类别: | Articles |
文件中的档案:
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.