New hybrid evolutionary algorithm for solving the bounded diameter minimum spanning tree problem

Given a connected, weighted, undirected graph G and a bound D, the bounded diameterminimum spanning tree (BDMST) problem seeks a spanning tree on G of minimum weight among the treesin which no path between two vertices contains more than D edges. This problem is NP-hard for 4 D |v| -1. In present paper a new randomized greedy heuristic algorithm for solving BDMST is proposed. Anevolutionary algorithm encodes spanning trees as lists of their edges, augmented with their center vertices.It applies operators that maintain the diameter bound and always generate valid offspring trees. Theseoperators are efficient, so the algorithm scales well to larger problem instances. On 25 Euclidean instancesof up to 1000 vertices, the EA improved substantially on solutions found by the randomized greedyheuristic.