Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorConsoli, S-
dc.contributor.authorDarby-Dowman, K-
dc.contributor.authorMladenović, N-
dc.contributor.authorMoreno-Perez, J A-
dc.description.abstractGiven a connected, undirected graph whose edges are labelled (or coloured), the minimum labelling spanning tree (MLST) problem seeks a spanning tree whose edges have the smallest number of distinct labels (or colours). In recent work, the MLST problem has been shown to be NP-hard and some effective heuristics (Modified Genetic Algorithm (MGA) and Pilot Method (PILOT)) have been proposed and analyzed. A hybrid local search method, that we call Group-Swap Variable Neighbourhood Search (GS-VNS), is proposed in this paper. It is obtained by combining two classic metaheuristics: Variable Neighbourhood Search (VNS) and Simulated Annealing (SA). Computational experiments show that GS-VNS outperforms MGA and PILOT. Furthermore, a comparison with the results provided by an exact approach shows that we may quickly obtain optimal or near-optimal solutions with the proposed heuristic.en
dc.format.extent362866 bytes-
dc.subjectCombinatorial optimizationen
dc.subjectGraphs and Networksen
dc.subjectLocal searchen
dc.subjectMinimum labelling spanning treesen
dc.titleSolving the minimum labelling spanning tree problem using hybrid local searchen
Appears in Collections:Publications
Dept of Mathematics Research Papers
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
GS-VNS.pdf354.36 kBAdobe PDFView/Open

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