Authors: Consoli, Sergio
Moreno Pérez, José Andrés
Mladenović, Nenad 
Title: Intelligent variable neighbourhood search for the minimum labelling spanning tree problem
Journal: Electronic Notes in Discrete Mathematics
Volume: 41
First page: 399
Last page: 406
Issue Date: 9-Jul-2013
ISSN: 1571-0653
DOI: 10.1016/j.endm.2013.05.118
Given 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 have been proposed and analyzed. In a currently ongoing project, we investigate an intelligent optimization algorithm to solve the problem. It is obtained by the basic Variable Neighbourhood Search heuristic with the integration of other complements from machine learning, statistics and experimental algorithmics, in order to produce high-quality performance and to completely automate the resulting optimization strategy. Computational experiments show that the proposed metaheuristic has high-quality performance for the MLST problem and it is able to obtain optimal or near-optimal solutions in short computational running time.
Keywords: Combinatorial optimization | Graphs and networks | Intelligent optimization | Minimum labelling spanning trees | Variable neighbourhood search
Publisher: Elsevier
Project: Spanish Ministry of Economy and Competitiveness (project TIN2012-32608)

Show full item record


checked on Jun 12, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




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