• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Approximating the max edge-coloring problem

Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2009), Approximating the max edge-coloring problem, in Fiala, Jiri; Kratochvil, Jan; Miller, Mirka, Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papers, Springer : Berlin, p. 83-94

Type
Communication / Conférence
Date
2009
Conference title
20th International Workshop on Combinatorial Algorithms, IWOCA 2009
Conference date
2009-07
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
Book author
Fiala, Jiri; Kratochvil, Jan; Miller, Mirka
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
5874
Published in
Berlin
ISBN
978-3-642-10216-5
Number of pages
480
Pages
83-94
Publication identifier
http://dx.doi.org/10.1007/978-3-642-10217-2_11
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Lucarelli, Giorgio cc
Milis, Ioannis
Paschos, Vangelis
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.
Subjects / Keywords
Max-edge-coloring; Approximation algorithms; Complexity

Related items

Showing items related by title and author.

  • Thumbnail
    Approximating the max edge-coloring problem 
    Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010) Article accepté pour publication ou publié
  • Thumbnail
    On the max-weight edge coloring problem 
    Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010) Article accepté pour publication ou publié
  • Thumbnail
    The max quasi-independent set problem 
    Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis; Pottié, Olivier (2012) Article accepté pour publication ou publié
  • Thumbnail
    The Max Quasi-Independent Set Problem 
    Pottié, Olivier; Paschos, Vangelis; Milis, Ioannis; Lucarelli, Giorgio; Giannakos, Aristotelis; Bourgeois, Nicolas (2010) Communication / Conférence
  • Thumbnail
    Improved approximation algorithms for the Max Edge-Coloring problem 
    Lucarelli, Giorgio; Milis, Ioannis (2011) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo