A new approach for the multiobjective minimum spanning tree (Preprint)

  <Reference List>
Type: Preprint
National /International: International
Title: A new approach for the multiobjective minimum spanning tree
Publication Date: 2017-12-19
Authors: - José Luis Esteves dos Santos
- Luigi Di Puglia Pugliese
- Francesca Guerriero
Abstract: In this paper, a new algorithm for the multiobjective minimum spanning tree problem is presented that can be used with any number of criteria. It is based on a labelling algorithm for the multiobjective shortest path problem in a transformed network. Some restrictions are added to the paths (minimal paths) in order to obtain a one-to-one correspondence between trees in the original network and minimal paths in the transformed one. The correctness of the algorithm is proved as well as a short example is presented. Finally, some computational experiments were reported showing the proposed method outperforms the others existing in the literature. A deep study is also done about the number of nondominated solutions and a statistical model is presented to predict its variation in the number of nodes and criteria. All the test instances used are available through the web page http://www.mat.uc.pt/∼zeluis/INVESTIG/MOMST/momst.htm
Institution: DMUC 17-53
Online version: http://www.mat.uc.pt...prints/eng_2017.html
Download: Not available
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support