Show simple item record

On the max-weight edge coloring problem

dc.contributor.authorLucarelli, Giorgio
HAL ID: 5944
ORCID: 0000-0001-7368-355X
dc.contributor.authorMilis, Ioannis
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-10-30T14:27:03Z
dc.date.available2009-10-30T14:27:03Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2373
dc.language.isoenen
dc.subjectWeighted edge coloringen
dc.subjectPolynomial algorithmsen
dc.subjectApproximation algorithmsen
dc.subject.ddc003en
dc.titleOn the max-weight edge coloring problemen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDepartment of Informatics, Athens University of Economics and Business;Grèce
dc.description.abstractenWe study the following generalization of the classical edge coloring problem: Given a weighted graph, find a partition of its edges into matchings (colors), each one of weight equal to the maximum weight of its edges, so that the total weight of the partition is minimized. We explore the frontier between polynomial and NP-hard variants of the problem, with respect to the class of the underlying graph, as well as the approximability of NP-hard variants. In particular, we present polynomial algorithms for bounded degree trees and star of chains, as well as an approximation algorithm for bipartite graphs of maximum degree at most twelve which beats the best known approximation ratios.en
dc.relation.isversionofjnlnameJournal of Combinatorial Optimization
dc.relation.isversionofjnlvol20en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages429-442en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s10878-009-9223-zen
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringer Netherlandsen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail
Name:
cahierLamsade248.pdf
Size:
317.2Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record