Relations, models and a memetic approach for three degree-dependent spanning tree problems

Abstract In this paper we take into account three different spanning tree problems with degree-dependent objective functions. The main application of these problems is in the field of optical network design. In particular, we propose the classical Minimum Leaves Spanning Tree problem as a relevant problem in this field and show its relations with the Minimum Branch Vertices and the Minimum Degree Sum Problems. We present a unified memetic algorithm for the three problems and show its effectiveness on a wide range of test instances.