New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree Problem
INFORMS Journal on Computing · 2015 · Volume 27 · Issue 1
Abstract
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.
Keywords
backbone, bounded-diameter minimum spanning tree problem, construction heuristics, diameter, optimization, spanning trees
Enable JavaScript for citation tools and additional paper interactions.