In this paper we present a novel coloring algorithm based on local search. We analyze its performance, and report several experimental results on DIMACS benchmark graphs. From our experiments, this algorithm looks robust, and yields a substantial speed up on previous algorithms for coloring. Our algorithm improves the best known coloring for four different DIMACS benchmark graphs: namely, Le450-25c, Le450-25d and Flat300_28_0 and Flat1000_76_0. Furthermore, we have run experiments on a simulator to get insights on its cache consciousness: from these experiments, it appears that the algorithm performs substantially less cache misses than other existing algorithms. © 2005 Elsevier B.V. All rights reserved.

CHECKCOL: Improved local search for graph coloring / Massimiliano, Caramia; Dell'Olmo, Paolo; Giuseppe F., Italiano. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - STAMPA. - 4:2(2006), pp. 277-298. [10.1016/j.jda.2005.03.006]

CHECKCOL: Improved local search for graph coloring

DELL'OLMO, Paolo;
2006

Abstract

In this paper we present a novel coloring algorithm based on local search. We analyze its performance, and report several experimental results on DIMACS benchmark graphs. From our experiments, this algorithm looks robust, and yields a substantial speed up on previous algorithms for coloring. Our algorithm improves the best known coloring for four different DIMACS benchmark graphs: namely, Le450-25c, Le450-25d and Flat300_28_0 and Flat1000_76_0. Furthermore, we have run experiments on a simulator to get insights on its cache consciousness: from these experiments, it appears that the algorithm performs substantially less cache misses than other existing algorithms. © 2005 Elsevier B.V. All rights reserved.
2006
combinatorial optimization; graph coloring; local search; local search algorithms
01 Pubblicazione su rivista::01a Articolo in rivista
CHECKCOL: Improved local search for graph coloring / Massimiliano, Caramia; Dell'Olmo, Paolo; Giuseppe F., Italiano. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - STAMPA. - 4:2(2006), pp. 277-298. [10.1016/j.jda.2005.03.006]
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/47647
 Attenzione

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

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