Show simple item record

dc.contributor.authorBourgeois, Nicolas
dc.contributor.authorLucarelli, Giorgio
HAL ID: 5944
ORCID: 0000-0001-7368-355X
dc.contributor.authorMilis, Ioannis
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-04-06T16:18:36Z
dc.date.available2010-04-06T16:18:36Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3868
dc.language.isoenen
dc.subjectMax-edge-coloringen
dc.subjectApproximation algorithms
dc.subjectComplexity
dc.subject.ddc003en
dc.titleApproximating the max edge-coloring problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe max edge-coloring problem is a natural weighted generalization of the classical edge-coloring problem arising in the domain of communication systems. In this problem each color class is assigned the weight of the heaviest edge in this class and the objective is to find a proper edge-coloring of the input graph minimizing the sum of all color classes’weights. We present new approximation results, that improve substantially the known ones,for several variants of the problem with respect to the class of the underlying graph.In particular,we deal with variants which either are known to be NP-hard(general and bipartite graphs)or are proven to be NP-hard in this paper(complete graphs with bi-valued edge weights)or their complexity question still remains open(trees).en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol411
dc.relation.isversionofjnlissue34-36
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages3055-3067
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2010.04.031
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record