Show simple item record

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

dc.contributor.authorde Werra, Dominique
dc.contributor.authorDemange, Marc
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-03-22T09:00:32Z
dc.date.available2011-03-22T09:00:32Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5778
dc.language.isoenen
dc.subjectAlgorithmsen
dc.subjectApproximabilityen
dc.subjectComplexityen
dc.subjectWeighted graphsen
dc.subjectSubcoloring problemen
dc.subject.ddc003en
dc.titleThe hypocoloring problem: complexity and approximability results when the chromatic number is smallen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages377-388en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber3353
dc.relation.ispartoftitleGraph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papersen
dc.relation.ispartofeditorHromkovic, Juraj
dc.relation.ispartofeditorNagl, Manfred
dc.relation.ispartofeditorWestfechtel, Bernhard
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2004
dc.relation.ispartofpages404en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/b104584en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-24132-4en
dc.relation.conftitle30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04)en
dc.relation.confdate2004-06
dc.relation.confcityBad Honnefen
dc.relation.confcountryAllemagneen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-540-30559-0_32


Files in this item

Thumbnail
Name:
hypercoloring.pdf
Size:
169.5Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record