Dynamic programming for spanning tree problems: application to the multi-objective case

The aim of this paper is to provide a dynamic programming formulation for the spanning tree problem (STP), which allows several instances of the classical STP to be addressed. The spanning tree structure is modelled with states and transition between states, defining a state-space. Several properties are shown and optimality conditions are given. Once the theoretical fundamentals of the proposed formulation are derived, the multi-objective spanning tree problem (MOSTP) is addressed. This problem arises in the telecommunications and transportation sectors. In these contexts, handling different criteria simultaneously plays a crucial role. The scientific literature provides several works that focus on the bi-objective version of the considered problem, in which only two criteria are taken into account. To the best of our knowledge, no works provide optimal methods to address the MOSTP with an arbitrary number l of objective functions. In this paper we extend the proposed dynamic programming formulation to model and solve the MOSTP with l >= 3 criteria.