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: Tijuana, Baja California change

14:00 - 15:15
Graph (Mediterranean Ballroom)Main Conference
Chair(s): Jiajia LiPacific Northwest National Laboratory
14:00
25m
Talk
Practical Parallel Hypergraph Algorithms
Main Conference
14:25
25m
Talk
A Supernodal All-Pairs Shortest Path Algorithm
Main Conference
piyush kumar saoOak Ridge National Lab, Ramki KannanOak Ridge National Laboratory, Prasun GeraGeorgia Institute of Technology, Rich VuducGeorgia Institute of Technology
14:50
25m
Talk
Increasing the Parallelism of Graph Coloring via Shortcutting
Main Conference
Ghadeer AlabandiTexas State University, Evan PowersTexas State University, Martin BurtscherTexas State University