On the Maximum Edge Coloring Problem (Extended Abstract)
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érenceDate
2009Conference title
6th International Workshop on Approximation and Online Algorithms, WAOA 2008Conference date
2008-09Conference city
KarlsruheConference country
AllemagneBook title
Approximation and Online Algorithms 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised PapersBook author
Bampis, Evripidis; Skutella, MartinPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
5426Published in
Berlin
ISBN
978-3-540-93979-5
Number of pages
293Pages
279-292
Publication identifier
Metadata
Show full item recordAbstract (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 problemRelated 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; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2009) Communication / Conférence
-
Escoffier, Bruno; Demange, Marc; de Werra, Dominique; Milis, Ioannis; Lucarelli, Giorgio; Paschos, Vangelis; Monnot, Jérôme (2008) Chapitre d'ouvrage
-
Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2007) Communication / Conférence