Weighted Coloring: further complexity and approximability results |
| |
Authors: | Bruno Escoffier Jérôme Monnot |
| |
Affiliation: | LAMSADE, CNRS and Université Paris-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France |
| |
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]. |
| |
Keywords: | Approximation algorithms NP-Complete problems Weighted coloring Interval graphs Line graph of bipartite graphs Partial k-tree |
本文献已被 ScienceDirect 等数据库收录! |
|