Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/44347
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
Serial title, monograph or event: Optimization Letters
Volume: 9
Issue: 3
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.
URI: http://hdl.handle.net/10316/44347
ISSN: 1862-4472 (Print) 1862-4480 (Online)
DOI: 10.1007/s11590-014-0759-1
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

SCOPUSTM   
Citations

7
checked on Nov 9, 2022

WEB OF SCIENCETM
Citations 10

7
checked on Jul 2, 2022

Page view(s)

213
checked on Nov 28, 2022

Download(s)

599
checked on Nov 28, 2022

Google ScholarTM

Check

Altmetric

Altmetric


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