Parallel Implementation of a Minimum Spanning Tree Algorithm

Abstract

Building a Minimum Spanning Tree (MST) of a weighted undirected graph is an important step in various applications, including circuit design, and it is desirable to build the MST quickly. However, current well-known approaches for building MSTs are not highly parallel. In this thesis, I propose a new algorithm to build MSTs in parallel. My new algorithm can be divided into two main steps: adding the ‘obvious edges’ of the MST and connecting the components produced by the first step. I parallelized both steps using various atomic operations. Two serial and two parallel MST implementations were used for performance comparisons. Based on the geometric mean over 14 graphs, my MST implementation is faster than the Edge Pruning MST approach but slower than Boost. Moreover, when run in parallel with 16 threads, my code is slower than both Galois and the Problem Based Benchmark Suite implementation.