Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431168 | Journal of Discrete Algorithms | 2006 | 22 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Massimiliano Caramia, Paolo Dell'Olmo, Giuseppe F. Italiano,