×

Weighted coloring: Further complexity and approximability results. (English) Zbl 1171.68611

Coppo, Mario (ed.) et al., Theoretical computer science. 9th Italian conference, ICTCS 2005, Siena, Italy, October 12–14, 2005. Proceedings. Berlin: Springer (ISBN 3-540-29106-7/pbk). Lecture Notes in Computer Science 3701, 205-214 (2005).
Summary: Given a vertex-weighted graph \(G = (V,E; w)\), \(w(v) \geq 0\) for any \(v \in V\), we consider a weighted version of the coloring problem which consists in finding a partition \(\mathcal S = (S_1,\ldots,S_k)\) of the vertex set \(V\) of \(G\) into stable sets and minimizing \(\sum_{i =1}^{k} w(S_i)\) where the weight of \(S\) is defined as \(\max\{w(v) : v \in 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, No. 2, 77–81 (1997)].
For the entire collection see [Zbl 1089.68004].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI