Output details
11 - Computer Science and Informatics
Middlesex University
A local search heuristic for bounded-degree minimum spanning trees
<12> The paper introduces a new genetic local search method for the bounded-degree minimum spanning tree problem, which is NP-complete, contrary to the unbounded case which is solvable in polynomial time. The new approach utilises parameter settings extracted from the analysis of partial fitness landscapes, where the fitness function is determined by the sum of Euclidean distances of nodes. The method is evaluated on ten randomly generated instances and compared to the LWRNG algorithm devised by Li and the EA algorithm proposed by Raidl and Julstrom. The genetic local search method achieves better results than LWRNG and EA on all seven larger problem settings.