Thumbnail

Approximation of MIN COLORING by moderately exponential algorithms

Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009), Approximation of MIN COLORING by moderately exponential algorithms, Information Processing Letters, 109, 16, p. 950-954. http://dx.doi.org/10.1016/j.ipl.2009.05.002

View/Open
Type
Article accepté pour publication ou publié
Date
2009
Journal name
Information Processing Letters
Volume
109
Number
16
Publisher
Elsevier
Pages
950-954
Publication identifier
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis
Abstract (EN)
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.
Subjects / Keywords
Approximation algorithms; Exponential algorithms; Min coloring problem