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 non-zero 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∈T w(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(n4) and O(n3) time, respectively. This paper introduces novel deterministic heuristics that produce comparable results in O(n2) time and lower cost trees in O(n3) time. Furthermore, meta-heuristics based on the randomised greedy approach are compared with an evolutionary algorithm based on the proposed heuristics using new operators.