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

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.