A better performance guarantee for approximate graph coloring |
| |
Authors: | Bonnie Berger and John Rompel |
| |
Affiliation: | (1) Laboratory for Computer Science, Massachusetts Institute of Technology, 02139 Cambridge, MA, USA |
| |
Abstract: | Approximate graph coloring takes as input a graph and returns a legal coloring which is not necessarily optimal. We improve the performance guarantee, or worst-case ratio between the number of colors used and the minimum number of colors possible, toO(n(log logn)3/(logn)3), anO(logn/log logn) factor better than the previous best-known result.The work of the first author was supported by Air Force Grant AFOSR-86-0078 and NSF PYI Grant 8657527-CCR. The work of the second author was supported by a National Science Foundation Graduate Fellowship. |
| |
Keywords: | Approximation algorithms Graph coloring Performance guarantee |
本文献已被 SpringerLink 等数据库收录! |