1. Weighted Coloring: further complexity and approximability results
- Author
-
Vangelis Th. Paschos, Jérôme Monnot, Bruno Escoffier, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Vertex (graph theory) ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,law.invention ,Combinatorics ,law ,Partial k-tree ,Line graph ,Partition (number theory) ,K-tree ,partial k-tree ,Mathematics ,021103 operations research ,Approximation algorithm ,Interval graph ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,line graph of bipartite graphs ,Computer Science Applications ,010201 computation theory & mathematics ,Signal Processing ,Bipartite graph ,interval graphs ,weighted coloring ,NP-complete problems ,Information Systems - 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 V of G into stable sets and minimizing k i=1 w(Si) 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).
- Published
- 2006
- Full Text
- View/download PDF