Show simple item record

dc.contributor.authorDemange, Marc
dc.contributor.authorde Werra, Dominique
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-03-22T14:47:51Z
dc.date.available2011-03-22T14:47:51Z
dc.date.issued2002
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5797
dc.language.isoenen
dc.subjectGraphsen
dc.subject.ddc003en
dc.titleWeighted node coloring: when stable sets are expensiveen
dc.typeCommunication / Conférence
dc.description.abstractenA version of weighted coloring of a graph is introduced: each node υ of a graph G = (V,E) is provided with a positive integer weight w(υ) and the weight of a stable set S of G is w(S) = maxw(υ) : υ ∈ V ∩ S. A k-coloring S = (S 1, . . . , S k) of G is a partition of V into k stable sets S 1, . . . , S k and the weight of S is w(S 1) + . . . + w(S k ). The objective then is to find a coloring S = (S 1, . . . , S k ) of G such that w(S 1) + . . . + w(S k ) is minimized. Weighted node coloring is NP-hard for general graphs (as generalization of the node coloring problem). We prove here that the associated decision problems are NP-complete for bipartite graphs, for line-graphs of bipartite graphs and for split graphs. We present approximation results for general graphs. For the other families of graphs dealt, properties of optimal solutions are discussed and complexity and approximability results are presented.en
dc.identifier.citationpages114-125en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber2573
dc.relation.ispartoftitleGraph-Theoretic Concepts in Computer Science 28th International Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, Revised Papersen
dc.relation.ispartofeditorKucera, Ludek
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2002
dc.relation.ispartofpages422en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/3-540-36379-3en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-00331-1en
dc.relation.conftitle28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'02)en
dc.relation.confdate2002-06
dc.relation.confcityCesky Krumloven
dc.relation.confcountryRépublique tchèqueen
dc.identifier.doihttp://dx.doi.org/10.1007/3-540-36379-3_11


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record