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.

An experimental study of simple, distributed vertex colouring algorithms / Finocchi, I.; Panconesi, A.; Silvestri, R.. - In: ALGORITHMICA. - ISSN 0178-4617. - 41:1(2004), pp. 1-23. [10.1007/s00453-004-1104-3]

An experimental study of simple, distributed vertex colouring algorithms

I. FINOCCHI;A. PANCONESI;
2004

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.
Distributed graph algorithms, Vertex coloring, Algorithm engineering
File in questo prodotto:
File Dimensione Formato  
ALGORITHMICA04.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 462.05 kB
Formato Adobe PDF
462.05 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/192563
Citazioni
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 17
social impact