Fast Minimum Spanning Tree Computation
Pawan Harish, P.J. Narayanan, Vibhav Vineet and Suryakant Patidar
In this chapter we present a GPU implementation of the minimum spanning tree (MST) algorithm for undirected graphs. Our application follows Boruvka’s approach to MST computation in a recursive manner and lays irregular data-dependent steps in terms of primitive operations using parallel scan, segmented scan, and split to achieve the reported high performance. The adaptation also provides an outlook on exploiting data-parallel primitives for nontrivial data-dependent algorithms.
Minimum spanning tree (MST) algorithms are useful as they find many tasks such as finding a minimum connected ...