| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428051 | Information Processing Letters | 2009 | 5 Pages |
Abstract
We study in this note approximation algorithms for the problem of coloring the vertices of a graph with as few colors as possible, with moderately exponential running times (and using either polynomial or exponential space), better than those of exact computation. Study of approximation is performed with respect to optimality measures, the minimum number of used colors and the maximum number of unused colors.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
