Max Edge Coloring of Trees

2009/01/26 by Giorgio Lucarelli, Lucarelli, Giorgio, Ioannis Milis +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.0901.4002

5 pages, 2 figures

arxiv created 2009/01/26 · arxiv updated 2009/12/01

Abstract

We study the weighted generalization of the edge coloring problem where the weight of each color class (matching) equals to the weight of its heaviest edge and the goal is to minimize the sum of the colors' weights. We present a 3/2-approximation algorithm for trees.

Related

• Bounded Max-Colorings of Graphs
• Improved Approximation Algorithms for Weighted Edge Coloring of Graphs
• Domination on Vertex-weighted Graphs Induce by a Coloring
• Coloring of Trees with Minimum Sum of Colors
• Edge-b-coloring Trees