Technical Report 2015-031

Deterministic Parallel Graph Coloring with Symmetry Breaking

Per Normann and Johan Öfverstedt

October 2015

Abstract:
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 symmetry breaking. The proposed algorithm is implemented and tested on standard problem instances from engineering applications and benchmarked against various 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 (303 kB, no cover)

Download BibTeX entry.