• 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

On the Maximum Edge Coloring Problem (Extended Abstract)

Thumbnail
Date
2009
Collection title
Lecture Notes in Computer Science
Collection Id
5426
Dewey
Recherche opérationnelle
Sujet
graphs; approximation algorithms; Coloring problem
DOI
http://dx.doi.org/10.1007/978-3-540-93980-1_22
Conference name
6th International Workshop on Approximation and Online Algorithms, WAOA 2008
Conference date
09-2008
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
Author
Bampis, Evripidis; Skutella, Martin
Publisher
Springer
Publisher city
Berlin
Year
2009
Pages number
293
ISBN
978-3-540-93979-5
Book URL
http://dx.doi.org/10.1007/978-3-540-93980-1
URI
https://basepub.dauphine.fr/handle/123456789/5295
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Lucarelli, Giorgio
Milis, Ioannis
Paschos, Vangelis
Type
Communication / Conférence
Item number of pages
279-292
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).

  • 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.