Comparison of algorithms for the Degree Constrained Minimum Spanning Tree

The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the prob lem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we devel op three heuristics for the DCMST, including simulated annealing, a genetic algorithm and a method based on problem space search. We propose alternati ve tree representations to facilitate the neighbourhood searches for the ge netic algorithm. The tree representation that we use for the genetic algori thm can be generalised to other tree optimisation problems as well. We comp are the computational performance of all of these approaches against the pe rformance of an exact solution approach in the literature. In addition, we also develop a new exact solution approach based on the combinatorial struc ture of the problem. We test all of these approaches using standard problem s taken from the literature and some new test problems that we generate.