Thumbnail

Improved Approximation Algorithms for the Max-Edge Coloring Problem

Lucarelli, Giorgio; Milis, Ioannis (2011), Improved Approximation Algorithms for the Max-Edge Coloring Problem, dans Marchetti-Spaccamela, Alberto; Segal, Michael, Theory and Practice of Algorithms in (Computer) Systems First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings, Springer : Berlin, p. 206-216. http://dx.doi.org/10.1007/978-3-642-19754-3_21

Voir/Ouvrir
Type
Communication / Conférence
Date
2011
Titre du colloque
First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011)
Date du colloque
2011-04
Ville du colloque
Rome
Pays du colloque
Italie
Titre de l'ouvrage
Theory and Practice of Algorithms in (Computer) Systems First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings
Auteurs de l’ouvrage
Marchetti-Spaccamela, Alberto; Segal, Michael
Éditeur
Springer
Titre de la collection
Lecture Notes in Computer Science
Numéro dans la collection
6595
Ville d’édition
Berlin
Isbn
978-3-642-19753-6
Nombre de pages
265
Pages
206-216
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Lucarelli, Giorgio cc
Milis, Ioannis
Résumé (EN)
The max edge-coloring problem asks for a proper edge-coloring of an edge-weighted graph minimizing the sum of the weights of the heaviest edge in each color class. In this paper we present a PTAS for trees and an 1.74-approximation algorithm for bipartite graphs; we also adapt the last algorithm to one for general graphs of the same, asymptotically, approximation ratio. Up to now, no approximation algorithm of ratio 2 − δ, for any constant δ> 0, was known for general or bipartite graphs, while the complexity of the problem on trees remains an open question.
Mots-clés
bipartite graphs; approximation algorithm; ptas; max edge-coloring problem