Variable neighborhood search for the degree-constrained minimum spanning tree problem

Given an undirected graph with weights associated with its edges, the degree-constrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to constraints on node degrees. We propose a variable neighborhood search heuristic for the degree-constrained minimum spanning tree problem, based on a dynamic neighborhood model and using a variable neighborhood descent iterative improvement algorithm for local search, Computational experiments illustrating the effectiveness of the approach on benchmark problems are reported. (C) 2002 Published by Elsevier Science B.V..