Name
Abstract | ||
|---|---|---|
We perform an extensive experimental evaluation of very simple, distributed, randomized algorithms for (Δ + 1)- and so-called Brooks-Vizing vertex colorings, i.e., colorings using considerably fewer than Δ colors. We consider variants of algorithms known from the literature, boosting them with a distributed independent set computation. Our study clearly determines the relative performance of the algorithms w.r.t. the number of communication rounds and the number of colors. The results are confirmed by all the experiments and instance families. The empirical evidence shows that some algorithms are extremely fast and very effective, thus being amenable to be used in practice. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.5555/545381.545461 | SODA |
Keywords | Field | DocType |
randomized algorithm,instance family,independent set computation,relative performance,communication round,vertex coloring algorithm,experimental analysis,so-called brooks-vizing vertex colorings,extensive experimental evaluation,empirical evidence,algorithms w,independent set | Randomized algorithm,Discrete mathematics,Algorithm engineering,Combinatorics,Vertex (geometry),Computer science,Algorithm,Independent set,Distributed algorithm,Boosting (machine learning),Interval arithmetic,Computation | Conference |
Volume | Issue | ISBN |
41 | 1 | 0-89871-513-X |
Citations | PageRank | References |
28 | 1.99 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irene Finocchi | 1 | 527 | 41.08 |
| Alessandro Panconesi | 2 | 1584 | 124.00 |
| Riccardo Silvestri | 3 | 1324 | 90.84 |