Date
2004
Collection title
Lecture Notes in Computer Science
Collection Id
3353
Dewey
Recherche opérationnelle
Sujet
Algorithms; Approximability; Complexity; Weighted graphs; Subcoloring problem
Conference name
30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04)
Conference date
06-2004
Conference city
Bad Honnef
Conference country
Allemagne
Book title
Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers
Author
Hromkovic, Juraj; Nagl, Manfred; Westfechtel, Bernhard
Publisher
Springer
Publisher city
Berlin
Year
2004
Pages number
404
ISBN
978-3-540-24132-4
Author
de Werra, Dominique
Demange, Marc
Monnot, Jérôme
Paschos, Vangelis
Type
Communication / Conférence
Item number of pages
377-388
Abstract (EN)
We consider a weighted version of the subcoloring problem that we call the hypocoloring problem: given a weighted graph G=(V,E;w) where w(v)S=(S1,¼,Sk)=(S1Sk) of the node set of G into hypostable sets and minimizing max{åv Î Kw(v)| K Î S}maxvKw(v) KS . Properties of hypocolorings are stated; complexity and approximability results are presented in some graph classes. The associated decision problem is shown to be NP-complete for bipartite graphs and triangle-free planar graphs with maximum degree 3. Polynomial algorithms are given for graphs with maximum degree 2 and for trees with maximum degree Delta.
