Intelligent variable neighbourhood search for the minimum labelling spanning tree problem |
| |
| Institution: | 1. Joint Research Centre, European Commission, Via Enrico Fermi 2749, 21027 Ispra (VA), Italy;2. DEIOC, IUDR, Universidad de La Laguna, Facultad de Matemáticas, 4a planta Astrofisico Francisco Sánchez s/n, 38271 Santa Cruz de Tenerife, Spain;3. School of Information Systems, Computing and Mathematics, Brunel University, Uxbridge, Middlesex, UB8 3PH, United Kingdom;1. Instituto de Matemática, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil;2. Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Buenos Aires, Argentina;1. Dept. of Computer Science and Engineering, Louisiana State University, Baton Rouge, LA 70803, USA;2. Dept. of Computer Science and Engineering, Heritage Institute of Technology, Kolkata, West Bengal 700 107, India;1. Department of Computer Science, Jinan University, Guangzhou, China;2. Facebook Inc., 7006 126th Ave NE, Kirkland, WA 98033, USA;3. South University of Science and Technology of China, Shenzhen, China;1. University of Thessaly, Lamia, Greece;2. Inria, France and Univ. Nice Sophia Antipolis, CNRS, I3S, Sophia Antipolis, France;3. Univ. Nice Sophia Antipolis, CNRS, I3S, Sophia Antipolis, France |
| |
| 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 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 minimum labelling spanning trees intelligent optimization variable neighbourhood search |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
