Moreno Pérez, José Andrés
|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||Abstract:||
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 Sep 26, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.