Write a Blog >>
Tue 25 Feb 2020 14:50 - 15:15 - Graph (Mediterranean Ballroom) Chair(s): Jiajia Li

Graph coloring is an assignment of colors to the vertices of a graph such that no two adjacent vertices get the same color. It is a key building block in many applications. Finding a coloring with a minimal number of colors is often only part of the problem. In addition, the solution also needs to be computed quickly. Several parallel implementations exist, but they may suffer from low parallelism depending on the input graph. We present an approach that increases the parallelism without affecting the coloring quality. On 18 test graphs, our technique yields an average of 3.4 times more parallelism. Our CUDA implementation running on a Titan V is 2.9 times faster on average and uses as few or fewer colors as the best GPU codes from the literature.

Tue 25 Feb
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

14:00 - 15:15: Main Conference - Graph (Mediterranean Ballroom)
Chair(s): Jiajia LiPacific Northwest National Laboratory
PPoPP-2020-papers14:00 - 14:25
PPoPP-2020-papers14:25 - 14:50
piyush kumar saoOak Ridge National Lab, Ramki KannanOak Ridge National Laboratory, Prasun GeraGeorgia Institute of Technology, Rich VuducGeorgia Institute of Technology
PPoPP-2020-papers14:50 - 15:15
Ghadeer AlabandiTexas State University, Evan PowersTexas State University, Martin BurtscherTexas State University