In this paper we propose a deterministic parallel graph coloring algorithm that enables Multi-Coloring in parallel for sparse undirected graphs by coarse-grained segmentation and auxiliary graph coloring. The proposed algorithm is implemented and tested on standard problem instances from engineering applications and benchmarked against various relevant deterministic graph coloring algorithms. Quantified results show that the proposed algorithm is competitive or better than the sequential Multi-Coloring algorithm with respect to execution time on multi-core architectures. The upper bound on the number of colors is guaranteed to be the same as for the Multi-Coloring algorithm.
Available as PDF (280 kB, no cover)
Download BibTeX entry.