Mini-project for COMP60621 - University of Manchester
Analysis and Implementation of a Parallel Version of Kruskal's Minimum Spanning Tree Algorithm using Helper Threads
The project provides an analysis and survey of the Kruskal algorithm for solving the Minimum Spanning Tree graph problem. Finding the Minimum Spanning Tree of a graph is important for optimizing and reducing costs in many contexts, such as computer networks, connecting components in a computer chip, simplifying circuits, wireless communications and medicine. The Minimum Spanning Tree problem has been long studied and today it is possible to find many alternatives of algorithms that have different characteristics. As the problem is usually costly to solve in terms of computation time, performance is of the essence and is the focus of this project. In particular, the algorithm presented serves as a simple alternative to extracting parallelism to Kruskal's algorithm on shared-memory architectures.
There are also other implementations of other popular MST algorithms and preliminary work on their parallel versions.