|
|||||
|
|
An improved approximation algorithm for maximum edge 2-coloring in simple graphs |
|
| Authors: | Zhi-Zhong Chen Ruka Tanahashi Lusheng Wang |
| Institution: | aDepartment of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan bDepartment of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong |
| 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 . This improves on the previous best (trivial) ratio of . |
| Keywords: | Approximation algorithms Maximum edge t-coloring Maximum b-matching Randomization Derandomization |
| 本文献已被 ScienceDirect 等数据库收录！ | |