New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree Problem

Given a bound, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of minimum total weight with a diameter not exceeding the given diameter bound. Depending on the tightness of the bound, optimal solutions have different structures. For loose bounds, optimal solutions are similar to the much easier minimum spanning tree problem, and greedy heuristics perform best. In contrast, these approaches fail for tight diameter bounds. This paper investigates how the structure of good solutions, and in particular their backbones, change depending on the diameter bound. Two new heuristics are then designed to overcome the shortcomings of existing approaches; required parameters are investigated; and the paper presents performance results for Euclidean BDMST instances.