Thumbnail

The hypocoloring problem: complexity and approximability results when the chromatic number is small

de Werra, Dominique; Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (2004), The hypocoloring problem: complexity and approximability results when the chromatic number is small, dans Hromkovic, Juraj; Nagl, Manfred; Westfechtel, Bernhard, Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Springer : Berlin, p. 377-388. http://dx.doi.org/10.1007/978-3-540-30559-0_32

Voir/Ouvrir
Type
Communication / Conférence
Date
2004
Titre du colloque
30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04)
Date du colloque
2004-06
Ville du colloque
Bad Honnef
Pays du colloque
Allemagne
Titre de l'ouvrage
Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers
Auteurs de l’ouvrage
Hromkovic, Juraj; Nagl, Manfred; Westfechtel, Bernhard
Éditeur
Springer
Titre de la collection
Lecture Notes in Computer Science
Numéro dans la collection
3353
Ville d’édition
Berlin
Isbn
978-3-540-24132-4
Nombre de pages
404
Pages
377-388
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
de Werra, Dominique
Demange, Marc
Monnot, Jérôme cc
Paschos, Vangelis
Résumé (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.
Mots-clés
Algorithms; Approximability; Complexity; Weighted graphs; Subcoloring problem