An Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms |
| |
Authors: | Irene Finocchi Alessandro Panconesi and Riccardo Silvestri |
| |
Affiliation: | (1) Department of Computer Science, Systems and Production, University of Rome Tor Vergata, Via del Politecnico 1, I-00133 Rome, Italy;(2) Department of Computer Science, University of Rome La Sapienza, Via Salaria 113, I-00198 Rome, Italy |
| |
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 (here denotes the maximum degree
of the graph). 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 with respect to 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 use very few rounds and are rather effective, thus being amenable to be used in practice. |
| |
Keywords: | Distributed graph algorithms Vertex coloring Algorithm engineering |
本文献已被 SpringerLink 等数据库收录! |
|