Approximating the maximum 2- and 3-edge-colorable subgraph problems ?
For a fixed value of a parameter k?2 k ? 2 , the Maximum k k -Edge-Colorable Subgraph Problem consists in finding k k edge-disjoint matchings in a simple graph, with the goal of maximising the total number of edges used. The problem is known to be APX -hard for all k k , but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as k k tends to infinity. Herein we propose improved approximation algorithms for the cases of k=2 k = 2 and k=3 k = 3 , having approximation ratios of 5/6 and 4/5, respectively.
approximation algorithm edge coloring of graphs k k -edge-colorable subgraph problem k k k k k