AMST: Accelerated Minimum Spanning Tree for Scalable Data
Chittaranjan Mohapatra, Nibedita Adhikari, B. N. B. Ray, Biswojit Nayak, Akshaya Kumar Dash · Indian Journal of Science and Technology · 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