Approximating the max edge-coloring problem
Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010), Approximating the max edge-coloring problem, Theoretical Computer Science, 411, 34-36, p. 3055-3067. http://dx.doi.org/10.1016/j.tcs.2010.04.031
TypeArticle accepté pour publication ou publié
Journal nameTheoretical Computer Science
MetadataShow full item record
Abstract (EN)The max edge-coloring problem is a natural weighted generalization of the classical edge-coloring problem arising in the domain of communication systems. In this problem each color class is assigned the weight of the heaviest edge in this class and the objective is to find a proper edge-coloring of the input graph minimizing the sum of all color classes’weights. We present new approximation results, that improve substantially the known ones,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).
Subjects / KeywordsMax-edge-coloring; Approximation algorithms; Complexity
Showing items related by title and author.
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis; Pottié, Olivier (2012) Article accepté pour publication ou publié