DC FieldValueLanguage
dc.contributor.authorConsoli, Sergioen
dc.contributor.authorDarby-Dowman, Kennethen
dc.contributor.authorMladenović, Nenaden
dc.contributor.authorMoreno Pérez, José Andrésen
dc.date.accessioned2020-05-02T16:42:10Z-
dc.date.available2020-05-02T16:42:10Z-
dc.date.issued2009-07-16en
dc.identifier.issn0377-2217en
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/2517-
dc.description.abstractThis paper studies heuristics for the minimum labelling spanning tree (MLST) problem. The purpose is to find a spanning tree using edges that are as similar as possible. Given an undirected labelled connected graph, the minimum labelling spanning tree problem seeks a spanning tree whose edges have the smallest number of distinct labels. This problem has been shown to be NP-hard. A Greedy Randomized Adaptive Search Procedure (GRASP) and a Variable Neighbourhood Search (VNS) are proposed in this paper. They are compared with other algorithms recommended in the literature: the Modified Genetic Algorithm and the Pilot Method. Nonparametric statistical tests show that the heuristics based on GRASP and VNS outperform the other algorithms tested. 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 heuristics.en
dc.publisherElsevier-
dc.relationMarie Curie Fellowship for Early Stage Researcher Training (EST-FP6), Grant no. MEST-CT-2004-006724-
dc.relationBrunel University (project NET-ACE)-
dc.relationSpanish Government, Grant no. TIN2005-08404-C04-03-
dc.relationCanary Government, Grant no. PI042005/044-
dc.relation.ispartofEuropean Journal of Operational Researchen
dc.subjectCombinatorial optimisation | Greedy Randomized Adaptive Search Procedure | Metaheuristics | Minimum labelling spanning tree | Variable Neighbourhood Searchen
dc.titleGreedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problemen
dc.typeArticleen
dc.identifier.doi10.1016/j.ejor.2008.03.014en
dc.identifier.scopus2-s2.0-58149473289en
dc.relation.firstpage440en
dc.relation.lastpage449en
dc.relation.issue2en
dc.relation.volume196en
dc.description.rankM21-
item.cerifentitytypePublications-
item.openairetypeArticle-
item.fulltextNo Fulltext-
item.grantfulltextnone-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
crisitem.author.orcid0000-0001-6655-0409-
Show simple item record

SCOPUSTM   
Citations

31
checked on Jul 12, 2024

Page view(s)

52
checked on May 9, 2024

Google ScholarTM

Check

Altmetric

Altmetric


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