• 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

On the Maximum Edge Coloring Problem (Extended Abstract)

Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2009), On the Maximum Edge Coloring Problem (Extended Abstract), in Bampis, Evripidis; Skutella, Martin, Approximation and Online Algorithms 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers, Springer : Berlin, p. 279-292. http://dx.doi.org/10.1007/978-3-540-93980-1_22

Type
Communication / Conférence
Date
2009
Conference title
6th International Workshop on Approximation and Online Algorithms, WAOA 2008
Conference date
2008-09
Conference city
Karlsruhe
Conference country
Allemagne
Book title
Approximation and Online Algorithms 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers
Book author
Bampis, Evripidis; Skutella, Martin
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
5426
Published in
Berlin
ISBN
978-3-540-93979-5
Number of pages
293
Pages
279-292
Publication identifier
http://dx.doi.org/10.1007/978-3-540-93980-1_22
Metadata
Show full item record
Author(s)
Lucarelli, Giorgio cc
Milis, Ioannis
Paschos, Vangelis
Abstract (EN)
We study the following generalization of the classical edge coloring problem: Given a weighted graph, find a partition of its edges into matchings (colors), each one of weight equal to the maximum weight of its edges, so that the total weight of the partition is minimized. We present new approximation algorithms 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
graphs; approximation algorithms; Coloring problem

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
    Approximating the max edge-coloring problem 
    Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2009) Communication / Conférence
  • Thumbnail
    Weighted edge coloring 
    Escoffier, Bruno; Demange, Marc; de Werra, Dominique; Milis, Ioannis; Lucarelli, Giorgio; Paschos, Vangelis; Monnot, Jérôme (2008) Chapitre d'ouvrage
  • Thumbnail
    On a generalized graph coloring/batch scheduling problem 
    Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2007) Communication / Conférence
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