Thumbnail

On the max-weight edge coloring problem

Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010), On the max-weight edge coloring problem, Journal of Combinatorial Optimization, 20, 4, p. 429-442. http://dx.doi.org/10.1007/s10878-009-9223-z

Voir/Ouvrir
Type
Article accepté pour publication ou publié
Date
2010
Nom de la revue
Journal of Combinatorial Optimization
Volume
20
Numéro
4
Éditeur
Springer Netherlands
Pages
429-442
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Lucarelli, Giorgio cc
Milis, Ioannis
Paschos, Vangelis
Résumé (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 explore the frontier between polynomial and NP-hard variants of the problem, with respect to the class of the underlying graph, as well as the approximability of NP-hard variants. In particular, we present polynomial algorithms for bounded degree trees and star of chains, as well as an approximation algorithm for bipartite graphs of maximum degree at most twelve which beats the best known approximation ratios.
Mots-clés
Weighted edge coloring; Polynomial algorithms; Approximation algorithms