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
TypeCommunication / Conférence
Conference titleFirst International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011)
Book titleTheory and Practice of Algorithms in (Computer) Systems First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings
Book authorMarchetti-Spaccamela, Alberto; Segal, Michael
Series titleLecture Notes in Computer Science
Number of pages265
MetadataShow full item record
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 / Keywordsbipartite graphs; approximation algorithm; ptas; max edge-coloring problem
Showing items related by title and author.
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2017) Article accepté pour publication ou publié