Thumbnail

Improved Approximation Algorithms for the Max-Edge Coloring Problem

Lucarelli, Giorgio; Milis, Ioannis (2011), Improved Approximation Algorithms for the Max-Edge Coloring Problem, in 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

View/Open
Type
Communication / Conférence
Date
2011
Conference title
First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011)
Conference date
2011-04
Conference city
Rome
Conference country
Italie
Book title
Theory and Practice of Algorithms in (Computer) Systems First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings
Book author
Marchetti-Spaccamela, Alberto; Segal, Michael
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
6595
Published in
Berlin
ISBN
978-3-642-19753-6
Number of pages
265
Pages
206-216
Publication identifier
Metadata
Show full item record
Author(s)
Lucarelli, Giorgio cc
Milis, Ioannis
Abstract (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.
Subjects / Keywords
bipartite graphs; approximation algorithm; ptas; max edge-coloring problem