标题:Approximating maximum edge 2-coloring in simple graphs
作者:Chen, Zhi-Zhong ;Konno, Sayuri ;Matsushita, Yuki
通讯作者:Chen, ZZ
作者机构:[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)
出版年:2010
卷:6124 LNCS
页码:78-89
DOI:10.1007/978-3-642-14355-7_9
摘要: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.
收录类别:EI
最新影响因子:0.302
资源类型:会议论文
TOP