Polynomial approximation and graph-coloring
Paschos, Vangelis (2003), Polynomial approximation and graph-coloring, Computing, 70, 1, p. 41-86. http://dx.doi.org/10.1007/s00607-002-1468-7
TypeArticle accepté pour publication ou publié
MetadataShow full item record
Abstract (EN)Consider a graph G=(V,E) of order n. In the minimum graph-coloring problem we try to color V with as few colors as possible so that no two adjacent vertices receive the same color. This problem is among the first ones proved to be intractable, and hence, it is very unlikely that an optimal polynomial-time algorithm could ever be devised for it. In this paper, we survey the main polynomial time approximation algorithms (the ones for which theoretical approximability bounds have been studied) for the minimum graph-coloring and we discuss their approximation performance and their complexity. Finally, we further improve the approximation ratio for graph-coloring.
Subjects / KeywordsGraph; Coloring; Complexity; NP-complete; Approximation algorithm
Showing items related by title and author.
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
de Werra, Dominique; Demange, Marc; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
Paschos, Vangelis; Grisoni, Pascal; Demange, Marc (1994) Article accepté pour publication ou publié
Paschos, Vangelis (2001) Article accepté pour publication ou publié
Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009) Article accepté pour publication ou publié