Show simple item record

Weighted coloring: further complexity and approximability results

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2009-10-06T11:55:26Z
dc.date.available2009-10-06T11:55:26Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2128
dc.language.isoenen
dc.subjectPartial k-treeen
dc.subjectLine graph of bipartite graphsen
dc.subjectInterval graphsen
dc.subjectWeighted coloringen
dc.subjectNP-Complete problemsen
dc.subjectApproximation algorithmsen
dc.subject.ddc003en
dc.titleWeighted coloring: further complexity and approximability resultsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven a vertex-weighted graph G = (V,E;w), w(v) ≥ 0 for any v ∈ V, we consider a weighted version of the coloring problem which consists in finding a partition S=(S1...,Sk)=(S1Sk) of the vertex set V of G into stable sets and minimizing ∑ i = 1 k w(S i ) where the weight of S is defined as max{w(v) : v ∈ 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(2):77-81 1997).
dc.relation.isversionofjnlnameInformation Processing Letters
dc.relation.isversionofjnlvol97en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2006
dc.relation.isversionofjnlpages98-103en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ipl.2005.09.013en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail
Name:
publi121.pdf
Size:
103.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record