Clustering the Data Points to Obtain Optimum Backbones for the Bounded Diameter Minimum Spanning Trees

Given a connected, weighted, undirected graph G containing V vertices and a bound D, the bounded diameter minimum spanning tree (BDMST) problem seeks a spanning tree on G of minimum weight among the trees in which no path between two vertices contains more than D edges. This problem is NP-hard for 4≤ D ≤ |v| -1. The current approaches that can be applied to very large instances such as OTTC and CTBC work reasonably well on instances with random edge costs, but on Euclidean instances this leads to a backbone of relatively short edges and the majority of the nodes have to be connected to this backbone via rather long edges. On the contrary, a reasonable solution for this instance, demands that the backbone should consist of a few longer edges to span the whole area to allow the large number of remaining nodes to be connected as leaves by much cheaper edges. In the present paper we introduce a new construction heuristic for the BDMST problem which is especially suited for very large Euclidean instances. It is based on modified k-means clustering that guides the Discriminatory-Randomized Greedy Heuristic (D-RGH) algorithm to find a good backbone. It maintains the diameter bound and always generates valid offspring trees besides scaling well to larger problem instances. On 25 Euclidean instances of up to 1000 vertices, the suggested heuristic improved substantially on solutions found by the DRGH. This approach is then further refined by a local improvement method.