Please use this identifier to cite or link to this item:
https://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: | https://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 | Size | Format | |
---|---|---|---|---|
MOSTP-DP_revisto.pdf | 396.58 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
9
checked on Oct 7, 2024
WEB OF SCIENCETM
Citations
10
8
checked on Oct 2, 2024
Page view(s)
270
checked on Oct 15, 2024
Download(s)
1,120
checked on Oct 15, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.