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, Irene; Panconesi, Alessandro; Silvestri, Riccardo. - In: ALGORITHMICA. - ISSN 0178-4617. - STAMPA. - 41:1(2004), pp. 1-23. [10.1007/s00453-004-1104-3]

An experimental study of simple, distributed vertex colouring algorithms

FINOCCHI, Irene;PANCONESI, Alessandro;SILVESTRI, RICCARDO
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.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/11573/241306
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 17
social impact