Please use this identifier to cite or link to this item:
Title: Dynamic programming for spanning tree problems: application to the multi-objective case
Authors: Di Puglia Pugliese, Luigi 
Guerriero, Francesca 
Santos, José Luis 
Keywords: Dynamic programming, Spanning tree problems, Multiple objective programming, Pareto front
Issue Date: 2015
Publisher: Springer Berlin Heidelberg
Abstract: The aim of this paper is to provide a dynamic programming formulation for the spanning tree problem (ST P), which allows several instances of the classical ST P 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 (MOST P) 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 theMOST P with an arbitrary number l of objective functions. In this paper we extend the proposed dynamic programming formulation to model and solve the MOST P with l ≥ 3 criteria.
ISSN: 1862-4472 (Print) 1862-4480 (Online)
Other Identifiers: 10.1007/s11590-014-0759-1
DOI: 10.1007/s11590-014-0759-1
Rights: embargoedAccess
Appears in Collections:I&D CMUC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat 
MOSTP-DP_revisto.pdf396.58 kBAdobe PDFView/Open
Show full item record


checked on Jun 25, 2019


checked on Jun 25, 2019

Page view(s)

checked on Jul 16, 2019


checked on Jul 16, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.