A better performance guarantee for approximate graph coloring |
| |
Authors: | Bonnie Berger 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|