Parallel Graph Voronoi Diagram on the GPU

Abstract

Graph Voronoi diagram has important applications in many network problems. We use the GPU computing framework Gunrock to solve the graph Voronoi diagram in parallel with a load balancing method. Experiments show that GPU algorithm has achieved good acceleration compared to CPU algorithm in large scale graphs of hundreds of thousands to millions of nodes. More importantly, the GPU algorithm is not sensitive to the number of Voronoi nodes. The execution time of the algorithm shows a slight downward trend with the increase of the number of Voronoi nodes.