On the max-weight edge coloring problem

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 explore the frontier between polynomial and NP-hard variants of the problem as well as the approximability of the NP-hard variants.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00948809
Author Lucarelli, Giorgio, Milis, Ioannis, Paschos, Vangelis
Maintainer CCSD
Last Updated May 6, 2026, 08:11 (UTC)
Created May 6, 2026, 08:11 (UTC)
Identifier hal-00948809
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Department of Informatics [Athens] (CS-AUEB) ; Mobile Multimedia Laboratory [Athens] ; Athens University of Economics and Business (AUEB)-Athens University of Economics and Business (AUEB)
creator Lucarelli, Giorgio
date 2007-03-23T00:00:00
harvest_object_id 23c02b56-fa0d-44cd-a4ec-a0c825068bd2
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-06-13T00:00:00
set_spec type:UNDEFINED