Variable neighbourhood search for the k-labelled spanning forest problem

In this paper we present an efficient Variable Neighbourhood Search for the k-labelled spanning forest (kLSF) problem, an NP-hard graph problem related to the minimum labelling spanning tree problem, and with strong implications in multimodal transportation networks. Given an undirected input graph whose edges are labelled, and an integer positive value , the aim is to find a spanning forest of the input graph having the minimum number of connected components and the upper bound on the number of labels to use.