• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

Year: 2023, Volume: 16, Issue: 37, Pages: 3110-3120

Original Article

AMST: Accelerated Minimum Spanning Tree for Scalable Data

Received Date:31 August 2023, Accepted Date:05 September 2023, Published Date:03 October 2023


Objectives: A traditional Minimum Spanning Tree (MST) is quite complex for large datasets concerning time and space complexities. So an Accelerated MST (AMST) is proposed for scalable data. Methods: AMST uses the k-means clustering to divide large data into a bunch of small-size data. The Delaunay Triangulation is applied to find the relationship among the data in O(nlogn) time for n points as compared to earlier approaches. A mid-point heuristic is designed to combine all clustered MSTs to get the MST for the original data. A refinement process is used for any mislaid of minimum weight edges. Findings: Several desirable properties of the AMST have been developed and compared with the results of existing literature. AMST is quite competitive in terms of time complexities, least weight error rate and accuracy for both large and small-size datasets. The mathematical analysis of the time complexity O(nlogn) proves that the proposed AMST has a 95% faster execution time than others. The proposed AMST has the least Weight Error Rate than other approaches which indicates that the cost is close to the exact Algorithms. The accuracy of the AMST is an average of 93% in different clustering accuracy indices which is similar to other approaches. Novelty: The execution time and accuracy prove that a faster MST can be developed to construct pins wire length routing in the promising field of VLSI (Very Large-Scale Integration) physical design.

Keywords: MST; Clustering; Delaunay Triangulation; Minimax Distance; Spectral Clustering; MidPoint Heuristic


  1. Jothi R, Mohanty SK, Ojha A. Fast approximate minimum spanning tree based clustering algorithm. Neurocomputing. 2018;272:542–557. Available from: https://doi.org/10.1016/j.neucom.2017.07.038
  2. Sandhu SS, Tripathy BK, Jagga S. KMST+: A K-Means++-Based Minimum Spanning Tree Algorithm. Smart Innovations in Communication and Computational Sciences. 2019;p. 113–127. Available from: https://doi.org/10.1007/978-981-10-8968-8_10
  3. Khan A, Aesha AA, Sarker J. A New Algorithmic Approach to Finding Minimum Spanning Tree. 2018 4th International Conference on Electrical Engineering and Information & Communication Technology (iCEEiCT). 2018;p. 590–594. Available from: https://doi.org/10.1109/CEEICT.2018.8628095
  4. Mishra G, Mohanty SK. A fast hybrid clustering technique based on local nearest neighbor using minimum spanning tree. Expert Systems with Applications. 2019;132:28–43. Available from: https://doi.org/10.1016/j.eswa.2019.04.048
  5. Berg MD, Kreveld MV, Overmars M, Schwarzkopf O. Computational Geometry: algorithms and applications . (Vol. 2) 1997.
  6. Funke D, Sanders P, Winkler V. Load-Balancing for Parallel Delaunay Triangulations. Lecture Notes in Computer Science. 2019;p. 156–169. Available from: https://doi.org/10.1007/978-3-030-29400-7_12
  7. Nguyen CM, Rhodes PJ. Delaunay triangulation of large-scale datasets using two-level parallelism. Parallel Computing. 2020;98:102672. Available from: https://doi.org/10.1016/j.parco.2020.102672
  8. Sharp N, Gillespie M, Crane K. Geometry processing with intrinsic triangulations. ACM SIGGRAPH 2021 Courses. 2021. Available from: https://doi.org/10.1145/3450508.3464592
  9. Mikhailov V, Pchenitchnyi P, Tagirov R, Khabibrakhmanov R, Shaimukhametov R. Analysis of algorithms for implementing Delaunay triangulation. 2021 International Conference on Information Technology and Nanotechnology (ITNT). 2021;p. 1–5. Available from: https://doi.org/10.1109/ITNT52450.2021.9649039
  10. Mathieson L, Moscato P. An Introduction to Proximity Graphs. Business and Consumer Analytics: New Ideas. 2019;p. 213–233. Available from: https://doi.org/10.1007/978-3-030-06222-4_4
  11. Ahmed M, Seraj R, Islam SMS. The k-means Algorithm: A Comprehensive Survey and Performance Evaluation. Electronics. 2020;9(8):1295. Available from: https://doi.org/10.3390/electronics9081295
  12. Wu G, Xu Y, Wu D, Ragupathy M, Mo YY, Chu C. Flip-flop clustering by weighted K-means algorithm. Proceedings of the 53rd Annual Design Automation Conference. 2016;p. 1–6. Available from: https://doi.org/10.1145/2897937.2898025
  13. Inaba M, Katoh N, Imai H. Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering. Proceedings of the tenth annual symposium on Computational geometry - SCG '94. 1994;p. 332–339. Available from: https://doi.org/10.1145/177424.178042
  14. Germiniani S, Pravadelli G. Exploiting clustering and decision-tree algorithms to mine LTL assertions containing non-boolean expressions. 2022 IFIP/IEEE 30th International Conference on Very Large Scale Integration (VLSI-SoC). 2022;p. 1–6. Available from: https://doi.org/10.1109/VLSI-SoC54400.2022.9939640
  15. Zhong C, Malinen M, Miao D, Fränti P. A fast minimum spanning tree algorithm based on K-means. Information Sciences. 2015;295:1–17. Available from: https://doi.org/10.1016/j.ins.2014.10.012
  16. Anita R, Subalalitha CN. An Approach to Cluster Tamil Literatures Using Discourse Connectives. 2019 IEEE 1st International Conference on Energy, Systems and Information Processing (ICESIP). 2019;p. 1–4. Available from: https://doi.org/10.1109/ICESIP46348.2019.8938315
  17. Radu RG, Radulescu IM, Truica CO, Apostol ES, Mocanu M. Clustering Documents using the Document to Vector Model for Dimensionality Reduction. 2020 IEEE International Conference on Automation, Quality and Testing, Robotics (AQTR). 2020;p. 1–6. Available from: https://doi.org/10.1109/AQTR49680.2020.9129967
  18. Mishra S, Moulik S, Prakash V. Invalid Scenarios of External Cluster Validity Indices: An Analysis Using Bell Polynomial. 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC). 2021;p. 2215–2220. Available from: https://doi.org/10.1109/SMC52423.2021.9659242
  19. Kim KH, Choi S. Neighbor search with global geometry: a minimax message passing algorithm. Proceedings of the 24th international conference on machine learning. 2007;p. 401–408. Available from: https://doi.org/10.1145/1273496.1273547
  20. Chehreghani MH. Efficient Computation of Pairwise Minimax Distance Measures. 2017 IEEE International Conference on Data Mining (ICDM). 2017;p. 799–804. Available from: https://doi.org/10.1109/ICDM.2017.95
  21. Yang Y, Shen F, Huang Z, Shen HT, Li X. Discrete Nonnegative Spectral Clustering. IEEE Transactions on Knowledge and Data Engineering. 2017;29(9):1834–1845. Available from: https://doi.org/10.1109/TKDE.2017.2701825


© 2023 Mohapatra et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Published By Indian Society for Education and Environment (iSee)


Subscribe now for latest articles and news.