Approximating the max edge-coloring problem
Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2009), Approximating the max edge-coloring problem, in Fiala, Jiri; Kratochvil, Jan; Miller, Mirka, Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papers, Springer : Berlin, p. 83-94
Type
Communication / ConférenceDate
2009Conference title
20th International Workshop on Combinatorial Algorithms, IWOCA 2009Conference date
2009-07Conference city
Hradec nad MoraviciConference country
République tchèqueBook title
Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected PapersBook author
Fiala, Jiri; Kratochvil, Jan; Miller, MirkaPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
5874Published in
Berlin
ISBN
978-3-642-10216-5
Number of pages
480Pages
83-94
Publication identifier
Metadata
Show full item recordAbstract (EN)
We study the weighted generalization of the edge coloring problem where the goal is to minimize the sum of the weights of the heaviest edges in the color classes. In particular, we deal with the approximability of this problem on bipartite graphs and trees. We first improve the best known approximation ratios for bipartite graphs of maximum degree ${\it \Delta} \geq 7$. For trees we present a polynomial 3/2-approximation algorithm, which is the first one for any special graph class with an approximation ratio less than the known ratio of two for general graphs. Also for trees, we propose a moderately exponential approximation algorithm that improves the 3/2 ratio with running time much better than that needed for the computation of an optimal solution.Subjects / Keywords
Max-edge-coloring; Approximation algorithms; ComplexityRelated items
Showing items related by title and author.
-
Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010) Article accepté pour publication ou publié
-
Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis; Pottié, Olivier (2012) Article accepté pour publication ou publié
-
Pottié, Olivier; Paschos, Vangelis; Milis, Ioannis; Lucarelli, Giorgio; Giannakos, Aristotelis; Bourgeois, Nicolas (2010) Communication / Conférence
-
Lucarelli, Giorgio; Milis, Ioannis (2011) Article accepté pour publication ou publié