Given a connected, undirected, weighted graph \(G = (V, E)\) in which the vertices are the co−ordinates of points in the Euclidean space and edge-weights are the Euclidean distances between those vertices, the Euclidean Leaf-Constrained Minimum Spanning Tree(e-LCMST) problem seeks to find a spanning tree of minimum cost that has at least the specified number of leaves L, where \(2 \le L \le |V|-1\) . The problem is NP-hard and has applications in domains such as Communication and Sensor Networks, Transportation, Power Distribution Networks, and VLSI. Several greedy heuristics and metaheuristic approaches have been proposed in the literature for solving this problem. This paper presents a fast clustering-based heuristic and two effective machine-learning-assisted hybrid metaheuristics for the problem. To effectively benchmark the results obtained by the algorithms, the paper also reports deviations, if any, from optimal solutions for small, fully connected Euclidean problem instances having up to 50 nodes, obtained using a simple Brute-force algorithm for the problem. In the course of several computational experiments, the proposed heuristic is shown to outperform the best-known heuristics extant in the literature on a wide range of benchmark instances. Results are also presented for problem sizes much larger than previously attempted in the literature, as well as on some real-world problem instances constructed as part of this work. Further, the proposed metaheuristics obtain competitive solution quality vis-á-vis the best-known metaheuristics for the problem and are shown to require significantly lesser computation time.
