Show simple item record

dc.contributor.authorBourgeois, Nicolas
dc.contributor.authorLucarelli, Giorgio
dc.contributor.authorMilis, Ioannis
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-12-14T13:57:31Z
dc.date.available2010-12-14T13:57:31Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5299
dc.language.isoenen
dc.subjectMax-edge-coloringen
dc.subjectApproximation algorithmsen
dc.subjectComplexityen
dc.subject.ddc003en
dc.titleApproximating the max edge-coloring problemen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.citationpages83-94en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber5874
dc.relation.ispartoftitleCombinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papersen
dc.relation.ispartofeditorFiala, Jiri
dc.relation.ispartofeditorKratochvil, Jan
dc.relation.ispartofeditorMiller, Mirka
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2009
dc.relation.ispartofpages480en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-10217-2en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/978-3-642-10217-2_11
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-10216-5en
dc.relation.conftitle20th International Workshop on Combinatorial Algorithms, IWOCA 2009en
dc.relation.confdate2009-07
dc.relation.confcityHradec nad Moravicien
dc.relation.confcountryRépublique tchèqueen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record