Parallel Implementation of a Minimum Spanning Tree Algorithm




Seo, Jarim

Journal Title

Journal ISSN

Volume Title



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.



Minimum spanning tree, Parallel


Seo, J. (2020). <i>Parallel implementation of a minimum spanning tree algorithm</i> (Unpublished thesis). Texas State University, San Marcos, Texas.


Rights Holder

Rights License

Rights URI