ECL-GC is a graph-coloring algorithm with shortcutting that is quite fast. The CUDA implementation thereof is quite fast and the C++/OpenMP implementation is quite fast on low-degree graphs. It operates on graphs stored in binary CSR format. Converters to this format as well as several already converted graphs can be found here.
Click on ECL-GC_12.cu and ECLgraph.h to download the CUDA code or on ECL-GC_12.cpp and ECLgraph.h to download the OpenMP C++ code. Click on one of the links below for a description of ECL-GC. Note that ECL-GC is protected by the license included in the beginning of the code.
The CUDA code can be compiled as follows:
nvcc -O3 -arch=sm_35 ECL-GC_12.cu -o ecl-gc
The OpenMP C++ code can be compiled as follows:
g++ -O3 -march=native -fopenmp ECL-GC_12.cpp -o ecl-gc
To compute the coloring of the file
graph.egr, enter (followed by the thread count for the OpenMP code):
G. Alabandi, E. Powers, and M. Burtscher. "Increasing the Parallelism of Graph Coloring via Shortcutting."
Proceedings of the 2020 ACM Conference on Principles and Practice of Parallel Programming, pp. 262-275. February 2020.
[pdf] [pptx] [video]
This work has been supported in part by the National Science Foundation under Grant No. 1406304 as well as by equipment donations from Nvidia Corporation.