Date
2009
Titre de la collection
Lecture Notes in Computer Science
n° dans la collection
5426
Indexation documentaire
Recherche opérationnelle
Subject
graphs; approximation algorithms; Coloring problem
Titre du colloque
6th International Workshop on Approximation and Online Algorithms, WAOA 2008
Date du colloque
09-2008
Ville du colloque
Karlsruhe
Pays du colloque
Allemagne
Titre de l'ouvrage
Approximation and Online Algorithms 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers
Auteur
Bampis, Evripidis; Skutella, Martin
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin
Année
2009
Nombre total de pages
293
ISBN
978-3-540-93979-5
Auteur
Lucarelli, Giorgio
Milis, Ioannis
Paschos, Vangelis
Type
Communication / Conférence
Nombre de pages du document
279-292
Résumé en anglais
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).
