Header menu link for other important links
X
KMST+: A K-Means++-Based Minimum Spanning Tree Algorithm
Sandhu S.S, , Jagga S.
Published in Springer Singapore
2019
Volume: 669
   
Pages: 113 - 127
Abstract
There are a number of algorithms that have been proposed in the graph theory literature to compute the minimum spanning tree of a given graph. These include the famous Prim’s and Kruskal’s algorithm, among others. The main drawback of these algorithms is their greedy nature, which means they cannot be applied to large datasets. In 2015, Zhong et al. proposed a fast MST (FMST) algorithm framework that uses K-means to find the MST with a reduced complexity of O(N1.5). In this paper, we have introduced an improved version of the FMST algorithm by using K-means++ to further increase the efficiency of the FMST algorithm. The use of K-means++ instead of K-means results in lesser complexity, faster convergence, and more accurate results during the clustering step which improves the accuracy of the MST formed. © Springer Nature Singapore Pte Ltd. 2019.
About the journal
JournalData powered by TypesetSmart Innovations in Communication and Computational Sciences Advances in Intelligent Systems and Computing
PublisherData powered by TypesetSpringer Singapore
ISSN2194-5357
Open Access0