ALCOMFT-TR-01-28

Massimiliano Caramia, Paolo Dell'Olmo and Giuseppe F. Italiano
CHECKCOL: Improved Local Search for Graph Coloring
Rome. Work package 5. March 2001.

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, and can be tuned in order to get to better performance. The results obtained justify also the fact that the running times of the new algorithm are very competitive for all our data sets.

Postscript file: ALCOMFT-TR-01-28.ps.gz (115 kb).