Article ID Journal Published Year Pages File Type
431682 Journal of Discrete Algorithms 2008 11 Pages PDF
Abstract

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of 468575. This improves on the previous best (trivial) ratio of 45.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
An improved approximation algorithm for maximum edge 2-coloring in simple graphs
Authors
, , ,