dc.contributor.author Bourgeois, Nicolas dc.contributor.author Lucarelli, Giorgio dc.contributor.author Milis, Ioannis dc.contributor.author Paschos, Vangelis dc.date.accessioned 2010-12-14T13:57:31Z dc.date.available 2010-12-14T13:57:31Z dc.date.issued 2009 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/5299 dc.language.iso en en dc.subject Max-edge-coloring en dc.subject Approximation algorithms en dc.subject Complexity en dc.subject.ddc 003 en dc.title Approximating the max edge-coloring problem en dc.type Communication / Conférence dc.description.abstracten We study the weighted generalization of the edge coloring problem where the goal is to minimize the sum of the weights of the heaviest edges in the color classes. In particular, we deal with the approximability of this problem on bipartite graphs and trees. We first improve the best known approximation ratios for bipartite graphs of maximum degree ${\it \Delta} \geq 7$. For trees we present a polynomial 3/2-approximation algorithm, which is the first one for any special graph class with an approximation ratio less than the known ratio of two for general graphs. Also for trees, we propose a moderately exponential approximation algorithm that improves the 3/2 ratio with running time much better than that needed for the computation of an optimal solution. en dc.identifier.citationpages 83-94 en dc.relation.ispartofseriestitle Lecture Notes in Computer Science dc.relation.ispartofseriesnumber 5874 dc.relation.ispartoftitle Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papers en dc.relation.ispartofeditor Fiala, Jiri dc.relation.ispartofeditor Kratochvil, Jan dc.relation.ispartofeditor Miller, Mirka dc.relation.ispartofpublname Springer en dc.relation.ispartofpublcity Berlin en dc.relation.ispartofdate 2009 dc.relation.ispartofpages 480 en dc.relation.ispartofurl http://dx.doi.org/10.1007/978-3-642-10217-2 en dc.relation.isversionofdoi http://dx.doi.org/10.1007/978-3-642-10217-2_11 dc.description.sponsorshipprivate oui en dc.subject.ddclabel Recherche opérationnelle en dc.relation.ispartofisbn 978-3-642-10216-5 en dc.relation.conftitle 20th International Workshop on Combinatorial Algorithms, IWOCA 2009 en dc.relation.confdate 2009-07 dc.relation.confcity Hradec nad Moravici en dc.relation.confcountry République tchèque en
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.