Maciej Besta and Armon Carigiet and Kacper Janda and Zur Vonarburg-Shmaria and Lukas Gianinazzi and Torsten Hoefler:
High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality
(In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC20), Nov. 2020)
Abstract
We develop the first parallel graph coloring
heuristics with strong theoretical guarantees on work and depth and coloring
quality. The key idea is to design a relaxation of the vertex degeneracy
order, a well-known graph theory concept, and to color vertices in the order
dictated by this relaxation. This introduces a tunable amount of parallelism
into the degeneracy ordering that is otherwise hard to parallelize. This
simple idea enables significant benefits in several key aspects of graph
coloring. For example, one of our algorithms ensures polylogarithmic depth
and a bound on the number of used colors that is superior to all other
parallelizable schemes, while maintaining workefficiency. In addition to
provable guarantees, the developed algorithms have competitive run-times for
several real-world graphs, while almost always providing superior coloring
quality. Our degeneracy ordering relaxation is of separate interest for
algorithms outside the context of coloring.
Documents
download article: download slides:
Recorded talk (best effort)
BibTeX
@inproceedings{besta-pgc, author={Maciej Besta and Armon Carigiet and Kacper Janda and Zur Vonarburg-Shmaria and Lukas Gianinazzi and Torsten Hoefler}, title={{High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality}}, year={2020}, month={Nov.}, booktitle={Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC20)}, source={http://www.unixer.de/~htor/publications/}, }
