Improved approximation algorithms for the Max Edge-Coloring problem

The Max Edge-Coloring problem asks for a proper edge-coloring of an edge-weighted graph minimizing the sum of the weights of the heaviest edges in the color classes. In this paper we present a PTAS for trees and a 1.74-approximation algorithm for bipartite graphs; we also adapt the last algorithm to...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2011-08, Vol.111 (16), p.819-823
Main Authors: Lucarelli, Giorgio, Milis, Ioannis
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Approximation algorithms
Asymptotic methods
Asymptotic properties
Color
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph coloring
Graph theory
Graphs
Information retrieval. Graph
Mathematical analysis
Mathematical problems
Mathematics
Max Edge-Coloring
Miscellaneous
Ratios
Sciences and techniques of general use
Studies
Theoretical computing
Trees
Trees, bipartite and general graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Max Edge-Coloring problem asks for a proper edge-coloring of an edge-weighted graph minimizing the sum of the weights of the heaviest edges in the color classes. In this paper we present a PTAS for trees and a 1.74-approximation algorithm for bipartite graphs; we also adapt the last algorithm to one for general graphs of the same, asymptotically, approximation ratio. ► We study the max edge-coloring problem of an edge-weighted graph. ► Minimize the sum of the weights of the heaviest edge in each color class. ► A PTAS for trees. ► A 1.74-approximation algorithm for bipartite graphs. ► An asymptotic 1.74-approximation algorithm for general graphs.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2011.05.019