Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431682 | Journal of Discrete Algorithms | 2008 | 11 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zhi-Zhong Chen, Ruka Tanahashi, Lusheng Wang,