Given an undirected graph whose edges are labeled or colored and have weights, and a budget B, the goal of the Cost Constrained Minimum Label Spanning Tree Problem(CCMLST) is to nd a spanning tree that uses the minimum number of labels while ensuring its cost does not exceed B. In the Label Constrained Minimum Spanning Tree Problem(LCMST), we are given a threshold K on the number of labels. The goal is to nd a minimum weight spanning tree that uses at most K distinct labels. In this paper, we present a Variable Neighborhood Search algorithm for the CCMLST and LCMST problems.

Keywords