摘要：AbstractIn thek-labeled Spanning Forest Problem (kLSF), given a graphGwith a label (color) assigned to each edge, and an integer positive valuekmaxwe look for the minimum number of connected components that can be obtained by using at mostkmaxdifferent labels. The problem is strictly related to the Minimum Labelling Spanning Tree Problem (MLST), since a spanning tree of the graph (i.e. a single connected component) would obviously be an optimal solution for the kLSF, if it can be obtained without violating the bound onkmax. In this work we present heuristic and exact approaches to solve this new problem.
