ISSN:
1432-0541
Keywords:
Approximation algorithms
;
Graph coloring
;
Performance guarantee
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01840398
Permalink