Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

BSP Implementation of Boruvka's Minimum Spanning Tree Algorithm

Abstract Details

2015, MS, Kent State University, College of Arts and Sciences / Department of Computer Science.
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.
Ye Zhao (Advisor)
Cheng-Chang Lu (Committee Member)
Ruoming Jin (Committee Member)
57 p.

Recommended Citations

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)