Minimum Spanning Tree Approach for Optimization and Clustering: Algorithms, Applications, and Comparisons

Abstract

Abstract This paper discusses various Minimum Spanning Tree (MST)-based approaches in a number of modern computing applications. The main focus includes an improved Kruskal algorithm (Zhang & Wang, 2022), MST clustering using a multi-objective genetic algorithm (Singh & Chauhan, 2021), MST-based wireless sensor network optimization (Liu & Zhao, 2023), MST-based anomaly detection in high-dimensional data (Li & Sun, 2020), and energy-efficient IoT routing using MST and clustering (Kaur & Sharma, 2022). Each method is described in detail, covering underlying principles, algorithms, and real-world applications. Related research findings are compared in a comparative table, and illustrative application examples are provided. The general findings show that optimized MST algorithms (e.g., improved Kruskal) can produce minimumcost trees with higher computational efficiency; MST-based clustering allows data partitioning without being constrained to specific cluster shapes; while integration of multi-objective genetic methods balances the conflict between minimizing intracluster distance and maximizing intercluster separation. MST applications in sensor and IoT networks exploit edge weights that incorporate energy and reliability factors, resulting in communication paths that are more energy efficient and secure. MST-based anomaly detection proves more sensitive to data manifold structures, outperforming traditional distance metrics on many benchmark datasets. Overall, this paper shows that MST utilization can be enhanced and applied across different domains to achieve diverse optimization objectives