Scatter search for the minimum leaf spanning tree problem. (September 2022)

• Record Type: Journal Article
• Authors: Kardam, Yogita Singh; Srivastava, Kamal; Jain, Pallavi; Martí, Rafael
• Is Part Of: Computers & operations research. Volume 145(2022)
• Publication Date: 2022-09
• Subjects: Spanning tree -- Metaheuristics -- Scatter search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105858
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Given an undirected connected graph G, the Minimum Leaf Spanning Tree Problem (MLSTP) consists in finding a spanning tree T of G with minimum number of leaves. This is an NP-hard problem with applications in communication and water supply networks. In this paper, we propose a heuristic algorithm to provide high-quality solutions (spanning trees with low number of leaves) for an input graph. Our heuristic is based on the scatter search methodology, and it combines different elements to perform an efficient search of the solution space. In particular, it applies both randomized and deterministic strategies in the construction methods to generate an initial set of solutions. A combination method specifically designed for trees coupled with two local searches with a diversity evaluation function, provides a good balance between search intensification and diversification. Experiments conducted on a large set of graphs indicate that our algorithm is able to generate spanning trees with a lower number of leaves than previous methods. Additionally, it is able to match the optimal solution in most of the instances for which it is known, outperforming the existing methods. Highlights: Solve a difficult graph problem with practical applications. Propose a new heuristic that performs better than previous ones. Analyze the elements of the scatter search methodology. Perform an empirical comparison with statistical tests.