On the Maximum Edge Coloring Problem (Extended Abstract)

Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis

Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2009), On the Maximum Edge Coloring Problem (Extended Abstract), in Bampis, Evripidis; Skutella, Martin, Approximation and Online Algorithms 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers, Springer : Berlin, p. 279-292. http://dx.doi.org/10.1007/978-3-540-93980-1_22

Type

Communication / Conférence

Date

2009

Conference title

6th International Workshop on Approximation and Online Algorithms, WAOA 2008

Conference date

2008-09

Conference city

Karlsruhe

Conference country

Allemagne

Book title

Approximation and Online Algorithms 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers

Book author

Bampis, Evripidis; Skutella, Martin

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

5426

Published in

Berlin

ISBN

978-3-540-93979-5

Number of pages

293

Pages

279-292

Abstract (EN)

We study the following generalization of the classical edge coloring problem: Given a weighted graph, find a partition of its edges into matchings (colors), each one of weight equal to the maximum weight of its edges, so that the total weight of the partition is minimized. We present new approximation algorithms 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 / Keywords

graphs; approximation algorithms; Coloring problem