WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS
| dc.citation.epage | 222 | en_US |
| dc.citation.issue | 3 | en_US |
| dc.citation.spage | 215 | en_US |
| dc.citation.volume | 63 | en_US |
| dc.citation.woscount | 14 | |
| dc.contributor.author | CHANG, GJ | en_US |
| dc.contributor.author | RANGAN, CP | en_US |
| dc.contributor.author | COORG, SR | en_US |
| dc.contributor.department | 應用數學系 | zh_TW |
| dc.contributor.department | Department of Applied Mathematics | en_US |
| dc.date.accessioned | 2014-12-08T15:03:00Z | |
| dc.date.available | 2014-12-08T15:03:00Z | |
| dc.date.issued | 1995-12-08 | en_US |
| dc.description.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. | en_US |
| dc.identifier.issn | 0166-218X | en_US |
| dc.identifier.journal | DISCRETE APPLIED MATHEMATICS | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/1601 | |
| dc.identifier.wosnumber | WOS:A1995TJ93600002 | |
| dc.language.iso | en_US | en_US |
| dc.title | WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS | en_US |
| dc.type | Article | en_US |