Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
DingChu_MS_Thesis_ETD.pdf (1.76 MB)
ETD Abstract Container
Abstract Header
BSP Implementation of Boruvka's Minimum Spanning Tree Algorithm
Author Info
Chu, Ding
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=kent1424483867
Abstract Details
Year and Degree
2015, MS, Kent State University, College of Arts and Sciences / Department of Computer Science.
Abstract
In this thesis, a parallel Minimum Spanning Tree algorithm (MST) is implemented under a Bulk Synchronous Parallel (BSP) graph computation platform. Given a graph with positive weights, MST problem is to find a minimum weight set of edges that connects all of the vertices. MST has been an interesting topic of graph theory for a long time and it has many applications: network design, approximation algorithm of Steiner Tree, cluster analysis, etc. There are classic algorithms of finding the MST. When it comes to the big graph, however, these options do not work very well. In the last decade, many efficient frameworks of dealing big data have been proposed: MapReduce, Pregel, etc. Moreover, the BSP graph processing system makes it possible to run the parallel graph algorithms even in a single machine. In this study, a parallel MST algorithm is implemented based on a BSP-like graph processing platform. In the implementation, there are some classic parallel algorithm design issues: leader selection, information synchronization, etc. One concrete example is provided to go through all the algorithm details. A detailed experimental evaluation is also attached which shows the algorithm performance and possible direction for future improvement.
Committee
Ye Zhao (Advisor)
Cheng-Chang Lu (Committee Member)
Ruoming Jin (Committee Member)
Pages
57 p.
Subject Headings
Computer Science
Keywords
BSP
;
MST
;
Boruvka
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
Chu, D. (2015).
BSP Implementation of Boruvka's Minimum Spanning Tree Algorithm
[Master's thesis, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1424483867
APA Style (7th edition)
Chu, Ding.
BSP Implementation of Boruvka's Minimum Spanning Tree Algorithm.
2015. Kent State University, Master's thesis.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=kent1424483867.
MLA Style (8th edition)
Chu, Ding. "BSP Implementation of Boruvka's Minimum Spanning Tree Algorithm." Master's thesis, Kent State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=kent1424483867
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
kent1424483867
Download Count:
3,158
Copyright Info
© 2015, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.