| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428957 | Information Processing Letters | 2006 | 6 Pages |
Abstract
Given a vertex-weighted graph G=(V,E;w), w(v)⩾0 for any v∈V, we consider a weighted version of the coloring problem which consists in finding a partition S=(S1,…,Sk) of the vertex set of G into stable sets and minimizing where the weight of S is defined as . In this paper, we continue the investigation of the complexity and the approximability of this problem by answering some of the questions raised by Guan and Zhu [D.J. Guan, X. Zhu, A coloring problem for weighted graphs, Inform. Process. Lett. 61 (2) (1997) 77–81].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
