O'Reilly logo

GPU Computing Gems Jade Edition by Wen-mei W. Hwu

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 7

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required