标题：Approximating maximum edge 2-coloring in simple graphs
作者：Chen, Zhi-Zhong ;Konno, Sayuri ;Matsushita, Yuki
作者机构：[Chen, Zhi-Zhong ;Konno, Sayuri ;Matsushita, Yuki ] Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan
会议名称：6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010
会议日期：July 19, 2010 - July 21, 2010
来源：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
摘要：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 roughly 0.842 and runs in O(n3m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was 5 6 &asyum; 0.833. © Springer-Verlag Berlin Heidelberg 2010.