A general variable neighborhood search approach for the minimum load coloring problem

The minimum load coloring problem consists of finding a 2-coloring function that assign either a color red or blue to each node of a graph such that the (maximum) load is minimized, i.e., to reduce as much as possible the number of edges with, at least, one endpoint colored in red (symmetrically, in blue). This NP-complete problem arises in Wavelength Division Multiplexing (WDM) technology and it has been used for broadcast WDM networks. In this paper, several procedures based on the Variable Neighborhood Search (VNS) methodology are proposed and compared on a set of random graphs and DIMACS benchmarks. Experimental results show that the proposed VNS variant exhibits a remarkable performance in comparison with the state-of-the-art methods. In particular, our approach achieves the best results in 48 out of 52 considered instances by employing, on average, less than 7 seconds. These results are further confirmed by conducting statistical tests.