Weighted coloring: further complexity and approximability results

Paschos, Vangelis; Escoffier, Bruno; Monnot, Jérôme

Paschos, Vangelis; Escoffier, Bruno; Monnot, Jérôme (2006), Weighted coloring: further complexity and approximability results, Information Processing Letters, 97, 3, p. 98-103. http://dx.doi.org/10.1016/j.ipl.2005.09.013

View/Open

publi121.pdf (103.9Kb)

Type

Article accepté pour publication ou publié

Date

2006

Journal name

Information Processing Letters

Volume

Number

Publisher

Elsevier

Pages

98-103

Abstract (EN)

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)=(S1Sk) of the vertex set V of G into stable sets and minimizing ∑ i = 1 k w(S i ) where the weight of S is defined as max{w(v) : v ∈ S}. In this paper, we keep on with the investigation of the complexity and the approximability of this problem by mainly answering one of the questions raised by D. J. Guan and X. Zhu (”A Coloring Problem for Weighted Graphs”, Inf. Process. Lett. 61(2):77-81 1997).

Subjects / Keywords

Partial k-tree; Line graph of bipartite graphs; Interval graphs; Weighted coloring; NP-Complete problems; Approximation algorithms