• 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

Approximating the max edge-coloring problem

Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010), Approximating the max edge-coloring problem, Theoretical Computer Science, 411, 34-36, p. 3055-3067. http://dx.doi.org/10.1016/j.tcs.2010.04.031

View/Open
max_edge-coloring.PDF (613.2Kb)
Type
Article accepté pour publication ou publié
Date
2010
Journal name
Theoretical Computer Science
Volume
411
Number
34-36
Publisher
Elsevier
Pages
3055-3067
Publication identifier
http://dx.doi.org/10.1016/j.tcs.2010.04.031
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Lucarelli, Giorgio cc
Milis, Ioannis
Paschos, Vangelis
Abstract (EN)
The max edge-coloring problem is a natural weighted generalization of the classical edge-coloring problem arising in the domain of communication systems. In this problem each color class is assigned the weight of the heaviest edge in this class and the objective is to find a proper edge-coloring of the input graph minimizing the sum of all color classes’weights. We present new approximation results, that improve substantially the known ones,for several variants of the problem with respect to the class of the underlying graph.In particular,we deal with variants which either are known to be NP-hard(general and bipartite graphs)or are proven to be NP-hard in this paper(complete graphs with bi-valued edge weights)or their complexity question still remains open(trees).
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 (2009) Communication / Conférence
  • 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