Experimental analysis of simple, distributed vertex coloring algorithms

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.