PERFORMANCE ANALYSIS OF MINIMUM SPANNING TREE ALGORITHMS

The Minimum-weight Spanning Tree Problem (MSTP) is one of the most well known problems of combinatorial optimization. It deals with finding the spanning tree of an undirected, connected graph, such that the sum of the weights of the selected edges is minimum. MSTP has direct applications in the design of computer and communication networks, power lines, telephone networks, wiring connections, links in a transportation network, piping, etc. It also occurs as a sub problem in the solution of other problems like approximation algorithms for the travelling salesman problem, the matching problem and the capacitated MST problem. MSTP has wide range of applications in various fields of science and technology, and hence the importance of analyzing and improving the performance of the various algorithms used to find the Minimum Spanning Tree is of great significance. This paper compares the efficiency of modern MST algorithms like Least Cost MST with the classical algorithms such as Prim's, Kruskal's and Borukva's algorithms.