Minimum Spanning Tree

Problem Description

This benchmark computes a minimum spanning tree in a weighted undirected graph with by using Boruvka's algorithm.


The algorithm is implemented by successive edge-relaxations of the minimum weight edges. However, since an explicit edge-relaxation involves modifying the graph, the implementation performs edge-relaxation indirectly. This is done by keeping track of the set of nodes that have been merged, called components, which avoids modifications to the graph. Each component's size grows in each iteration, while the number of components reduces (due to components getting merged). The algorithm terminates when only one component remains. When the input graph is disconnected, the algorithm terminates when the number of components does not change in an iteration and it computes a minimum spanning forest.

Figure: Before edge-contraction and after edge-contraction

The computation is split across a sequence of kernels. This program is generated by IrGL compiler.

do {
  find the minimum weight edge out of each component;
  merge a component with its partner;
} while the number of components changes;
NOTE: Only use the symmetric graph files ( as inputs.


GraphTime (ms)
USA-road-d.CTR 11
USA-road-d.W 138
USA-road-d.USA 663
orkut 964
livejournal 3074
indochina 2173

The above performance is observed on a 1733.500 Mhz GeForce GTX 1080 6000 with 8119 MB of main memory.