Authors: Consoli, Sergio
Moreno Pérez, José Andrés
Mladenović, Nenad 
Title: Intelligent optimization for the minimum labelling spanning tree problem
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 7997 LNCS
First page: 19
Last page: 23
Conference: 7th International Conference on Learning and Intelligent Optimization, LION 7; Catania; Italy; 7 January 2013 through 11 January 2013
Issue Date: 30-Dec-2013
ISBN: 978-3-642-44972-7
ISSN: 0302-9743
DOI: 10.1007/978-3-642-44973-4_2
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 analysed. In this paper we present preliminary results of a currently on-going project regarding the implementation of an intelligent optimization algorithm to solve the MLST problem. This algorithm 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.
Keywords: Combinatorial optimization | Graphs and networks | Hybrid local search | Intelligent optimization | Minimum labelling spanning trees
Publisher: Springer Link

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.