Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ipl.2009.05.002 | Inf. Process. Lett. |
Keywords | Field | DocType |
exact computation,exponential algorithm,minimum number,used color,note approximation algorithm,maximum number,unused color,exponential space,min coloring,approximation algorithms | Discrete mathematics,Approximation algorithm,Complete coloring,Edge coloring,Combinatorics,Exponential function,Fractional coloring,Polynomial,Algorithm,Greedy coloring,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
109 | 16 | 0020-0190 |
Citations | PageRank | References |
8 | 0.46 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Bourgeois | 1 | 99 | 7.96 |
| Bruno Escoffier | 2 | 430 | 37.32 |
| Vangelis Th. Paschos | 3 | 633 | 63.97 |