• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Approximating the max edge-coloring problem

Thumbnail
Date
2009
Collection title
Lecture Notes in Computer Science
Collection Id
5874
Dewey
Recherche opérationnelle
Sujet
Max-edge-coloring; Approximation algorithms; Complexity
DOI
http://dx.doi.org/10.1007/978-3-642-10217-2_11
Conference name
20th International Workshop on Combinatorial Algorithms, IWOCA 2009
Conference date
07-2009
Conference city
Hradec nad Moravici
Conference country
République tchèque
Book title
Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papers
Author
Fiala, Jiri; Kratochvil, Jan; Miller, Mirka
Publisher
Springer
Publisher city
Berlin
Year
2009
Pages number
480
ISBN
978-3-642-10216-5
Book URL
http://dx.doi.org/10.1007/978-3-642-10217-2
URI
https://basepub.dauphine.fr/handle/123456789/5299
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bourgeois, Nicolas
Lucarelli, Giorgio
Milis, Ioannis
Paschos, Vangelis
Type
Communication / Conférence
Item number of pages
83-94
Abstract (EN)
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.