• Home
• People
• Jobs
• Visit
• Thesis Topics
• Publications
• Conference Rankings
• Research
• Bcast
• Teaching
• Contact

SPONSORS

COLLABORATIONS

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

M. Besta, A. Carigiet, K. Janda, Z. Vonarburg-Shmaria, L. Gianinazzi, T. 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), presented in , , ISBN: , 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: access preprint on arxiv: 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={11},   booktitle={Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC20)},   location={},   publisher={},   isbn={},   note={},   doi={}, }