Deterministic Heuristics and an Evolutionary Algorithm for the Bounded Diameter Minimum Spanning Tree Problem

Given a connected, undirected graph G = (V, E) on ∣V∣ vertices, an integer bound D ≥ 2 and nonzero edge costs associated with each edge e ∈ E, a bounded-diameter spanning tree (BDST) is defined as a spanning tree T ⊆ E on G with tree diameter no greater than D. The bounded diameter minimum spanning tree problem finds a BDST of minimum edge cost w(T) = Σ_∀e∈Tw(e). This combinatorial optimisation problem, which finds application in the areas of data compression, distributed mutual exclusion and ad hoc networks, is known to be NP-Hard for 4 ≤ D < n – 1, where n is the number of vertices and D the diameter bound. Well known deterministic and randomised greedy algorithms compute approximate solutions in O(n⁴) and O (n³) time, respectively. This paper introduces novel deterministic heuristics that produce comparable results in O(n²) time and lower cost trees in O(n³) time. Furthermore, meta-heuristics based on the randomised greedy approach are compared with an evolutionary algorithm based on the proposed heuristics using new operators.