Show simple item record

dc.contributor.advisorBurtscher, Martin
dc.contributor.authorSeo, Jarim ( Orcid Icon 0000-0002-5023-5284 )
dc.date.accessioned2020-11-14T20:57:55Z
dc.date.available2020-11-14T20:57:55Z
dc.date.issued2020-12
dc.identifier.citationSeo, J. (2020). Parallel implementation of a minimum spanning tree algorithm (Unpublished thesis). Texas State University, San Marcos, Texas.
dc.identifier.urihttps://digital.library.txstate.edu/handle/10877/12921
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.formatText
dc.format.extent40 pages
dc.format.medium1 file (.pdf)
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
txstate.documenttypeThesis
dc.contributor.committeeMemberQasem, Apan
dc.contributor.committeeMemberGao, Byron
thesis.degree.departmentComputer Science
thesis.degree.disciplineComputer Science
thesis.degree.grantorTexas State University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science
dc.description.departmentComputer Science


Download

Thumbnail

This item appears in the following Collection(s)

Show simple item record