Please use this identifier to cite or link to this item:
http://hdl.handle.net/10071/12779
Author(s): | Salgueiro, R. de Almeida, A. Oliveira, O. |
Date: | 2017 |
Title: | New genetic algorithm approach for the min-degree constrained minimum spanning tree |
Volume: | 258 |
Number: | 3 |
Pages: | 877 - 886 |
ISSN: | 0377-2217 |
DOI (Digital Object Identifier): | 10.1016/j.ejor.2016.11.007 |
Keywords: | Combinatorial optimization Degree-constrained spanning tree Genetic algorithm Heuristic Lower bound |
Abstract: | A novel approach is proposed for the NP-hard min-degree constrained minimum spanning tree (md-MST). The NP-hardness of the md-MST demands that heuristic approximations are used to tackle its intractability and thus an original genetic algorithm strategy is described using an improvement of the Martins-Souza heuristic to obtain a md-MST feasible solution, which is also presented. The genetic approach combines the latter improvement with three new approximations based on different chromosome representations for trees that employ diverse crossover operators. The genetic versions compare very favourably with the best known results in terms of both the run time and obtaining better quality solutions. In particular, new lower bounds are established for instances with higher dimensions. |
Peerreviewed: | yes |
Access type: | Open Access |
Appears in Collections: | CTI-RI - Artigos em revistas científicas internacionais com arbitragem científica |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
EJOR_v7_elsarticle.pdf | Pré-print | 533,8 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.