Name
Abstract | ||
|---|---|---|
The chromatic sum of a graph G is the smallest total among all proper colorings of G using natural numbers. It was shown that
computing the chromatic sum is NP-hard. In this article we prove that a simple greedy algorithm applied to sparse graphs gives
a "good" approximation of the chromatic sum. For all graphs the existence of a polynomial time algorithm that approximates
the chromatic sum with a linear function error implies P = NP.
|
Year | DOI | Venue |
|---|---|---|
1989 | 10.1007/BFb0038467 | Great Lakes Computer Science Conference |
Keywords | Field | DocType |
approximation algorithms,chromatic sum,greedy algorithm | Discrete mathematics,Approximation algorithm,Dinic's algorithm,Combinatorics,Simplex algorithm,Chromatic scale,Nondeterministic algorithm,Greedy algorithm,Time complexity,Criss-cross algorithm,Mathematics | Conference |
Volume | ISSN | ISBN |
507 | 0302-9743 | 3-540-97628-0 |
Citations | PageRank | References |
20 | 2.05 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ewa Kubicka | 1 | 66 | 9.61 |
| Grzegorz Kubicki | 2 | 95 | 15.16 |
| Dionysios Kountanis | 3 | 59 | 8.57 |