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
TypeArticle accepté pour publication ou publié
Journal nameInformation Processing Letters
MetadataShow full item record
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 / KeywordsApproximation algorithms; Exponential algorithms; Min coloring problem
Showing items related by title and author.
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié