Revisiting search methods for the Bounded-Diameter Minimum Spanning Tree Problem

¹ Instituto Federal do Triângulo Mineiro, Uberaba, MG, Brazil
² Universidade do Estado do Rio de Janeiro, Rio de Janeiro, RJ, Brazil
³ Universidade Federal Fluminense, Niterói, RJ, Brazil
⁴ Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 19 April 2024
Accepted: 30 January 2025

Abstract

The Bounded-Diameter Minimum Spanning Tree Problem (BDMSTP) is defined as follows: Given a graph G where each edge xy has a positive cost w_xy the goal is to find an optimal spanning tree of G whose diameter does not exceed a prescribed positive integer D≤2. Applications of the BDMSTP appear in telecommunication network and fiber optic projects, data compression problems, and distributed systems design. This work revisits search methods for the BDMSTP and proposes alternative combinations of local search moves, intending to select efficient sets of moves and improve the quality of the solutions found in the literature. For small 50-and 100-node instances from the widely-used OR-Library, we obtain exact solutions whose optimal values were so far unknown. Having solved these easier cases, we can then concentrate our efforts on solving more challenging OR-Library graph instances with 250, 500, and 1000 nodes. The process of selecting efficient sets of search moves is done by encapsulating different local search versions (based on the Variable Neighborhood Descent method) in an ILS approach. Some new neighborhoods are also proposed. Computational tests show that these neighborhoods allowed the proposed ILS approach to obtain better results than those presented in the literature.