Parallel Implementation of a Minimum Spanning Tree Algorithm

Simple item page
dc.contributor.advisorBurtscher, Martin
dc.contributor.authorSeo, Jarim
dc.contributor.committeeMemberQasem, Apan
dc.contributor.committeeMemberGao, Byron
dc.date.accessioned2020-11-14T20:57:55Z
dc.date.available2020-11-14T20:57:55Z
dc.date.issued2020-12
dc.description.abstractBuilding 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.
dc.description.departmentComputer Science
dc.formatText
dc.format.extent40 pages
dc.format.medium1 file (.pdf)
dc.identifier.citationSeo, J. (2020). <i>Parallel implementation of a minimum spanning tree algorithm</i> (Unpublished thesis). Texas State University, San Marcos, Texas.
dc.identifier.urihttps://hdl.handle.net/10877/12921
dc.language.isoen
dc.subjectMinimum spanning tree
dc.subjectParallel
dc.subject.lcshParallel processing (Electronic computers)
dc.subject.lcshSpanning trees (Graph theory)
dc.titleParallel Implementation of a Minimum Spanning Tree Algorithm
dc.typeThesis
thesis.degree.departmentComputer Science
thesis.degree.disciplineComputer Science
thesis.degree.grantorTexas State University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
SEO-THESIS-2020.pdf
Size:
1.53 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.52 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
2.96 KB
Format:
Plain Text
Description:
Download

Collections

Graduate Theses and Dissertations