Approximating maximum edge 2-coloring in simple graphs
We present a polynomialtime approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 0.842 and runs in O(n3m) O ( n 3 m ) time, where n n (respectively, m m ) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomialtime approximation algorithm was 5 6 ? 0.833 .
approximation algorithms graph algorithms edge coloring np-hardness