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.
7.1 Introduction, Problem Statement, and Context
Minimum spanning tree (MST) algorithms are useful as they find many tasks such as finding a minimum connected ...
Get GPU Computing Gems Jade Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
