Weighted coloring: further complexity and approximability results

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

Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2005), Weighted coloring: further complexity and approximability results, in Pinna, G. Michele; Lodi, Elena; Coppo, Mario, Theoretical Computer Science 9th Italian Conference, ICTCS 2005, Siena, Italy, October 12-14, 2005, Proceedings, Springer : Berlin, p. 205-214. http://dx.doi.org/10.1007/11560586_17

View/Open

weighted_coloring.PDF (140.2Kb)

Type

Communication / Conférence

Date

2005

Conference title

9th Italian Conference on Theoretical Computer Science (ICTCS'05)

Conference date

2005-10

Conference city

Sienne

Conference country

Italie

Book title

Theoretical Computer Science 9th Italian Conference, ICTCS 2005, Siena, Italy, October 12-14, 2005, Proceedings

Book author

Pinna, G. Michele; Lodi, Elena; Coppo, Mario

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

3701

Published in

Berlin

ISBN

978-3-540-29106-0

Number of pages

411

Pages

205-214

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

Approximation algorithm; NP-complete problems; weighted coloring; interval graphs; line graph of bipartite graphs; partial k-tree