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

•We study three spanning tree problems with degree-dependent objective functions.•Finding the ST with fewest leaves is proven to be relevant for optical networks.•Several relations among the three problems are demonstrated.•We propose mathematical models and a memetic approach for the problems.•We show the effectivity of the proposed approach on test instances.

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.