Uppsala University Department of Information Technology

Technical Report 2015-035

Deterministic Parallel Graph Coloring with Repartitioning by Auxiliary Graph Coloring

Johan Öfverstedt and Per Normann

December 2015

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.

Uppsala Universitet