Show simple item record

Improved Approximation Algorithms for the Max-Edge Coloring Problem

dc.contributor.authorLucarelli, Giorgio
HAL ID: 5944
ORCID: 0000-0001-7368-355X
dc.contributor.authorMilis, Ioannis
dc.date.accessioned2011-04-26T16:55:28Z
dc.date.available2011-04-26T16:55:28Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6057
dc.language.isoenen
dc.subjectbipartite graphsen
dc.subjectapproximation algorithmen
dc.subjectptasen
dc.subjectmax edge-coloring problemen
dc.subject.ddc003en
dc.titleImproved Approximation Algorithms for the Max-Edge Coloring Problemen
dc.typeCommunication / Conférence
dc.description.abstractenThe max edge-coloring problem asks for a proper edge-coloring of an edge-weighted graph minimizing the sum of the weights of the heaviest edge in each color class. In this paper we present a PTAS for trees and an 1.74-approximation algorithm for bipartite graphs; we also adapt the last algorithm to one for general graphs of the same, asymptotically, approximation ratio. Up to now, no approximation algorithm of ratio 2 − δ, for any constant δ> 0, was known for general or bipartite graphs, while the complexity of the problem on trees remains an open question.en
dc.identifier.citationpages206-216en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber6595
dc.relation.ispartoftitleTheory and Practice of Algorithms in (Computer) Systems First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedingsen
dc.relation.ispartofeditorMarchetti-Spaccamela, Alberto
dc.relation.ispartofeditorSegal, Michael
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2011
dc.relation.ispartofpages265en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-19754-3en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-19753-6en
dc.relation.conftitleFirst International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011)en
dc.relation.confdate2011-04
dc.relation.confcityRomeen
dc.relation.confcountryItalieen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-19754-3_21


Files in this item

Thumbnail
Name:
CahierLamsade301.PDF
Size:
188.8Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record