Fast Minimum Spanning Tree Computation
The code computes minimum spanning tree on CUDA using primitives in accordance to the algorithm given in Chapter 7 of GPU Computing Gems, Jade Edition, 2011. It extends the Boruvka’s approach to MST to a recursive framework and maps basic steps of the algorithm to data parallel primitives (scan, segmented scan, split/sort). The package includes files explaining the input graph format, a sample graph for testing purpose and a converter to convert DIMACS graph format into the input format. The code uses CUDPP for scan and segmented min scan operations and the Thrust library for sorting primitives. This variation of the code does not do duplicate edge removal.
|RecMST - No Duplicate Edge Removal.zip||64.88 KB|