Parallel Implementation of a Minimum Spanning Tree Algorithm
Date
2020-12
Authors
Seo, Jarim
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Minimum spanning tree, Parallel
Citation
Seo, J. (2020). <i>Parallel implementation of a minimum spanning tree algorithm</i> (Unpublished thesis). Texas State University, San Marcos, Texas.