Approximating the max edge-coloring problem

Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis

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érence

Date

2009

Conference title

20th International Workshop on Combinatorial Algorithms, IWOCA 2009

Conference date

2009-07

Conference city

Hradec nad Moravici

Conference country

République tchèque

Book title

Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papers

Book author

Fiala, Jiri; Kratochvil, Jan; Miller, Mirka

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

5874

Published in

Berlin

ISBN

978-3-642-10216-5

Number of pages

480

Pages

83-94

Abstract (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; Complexity