I am working on a simulated annealing algorithm for graph coloring. The model I follow is the following: http://riad.pk.edu.pl/~zk/pubs/PPAM07_2.pdf. I have troubles understanding the cooling schedule and more particularly, the part with the variable M. In my understanding M represents the number of iterations after which the temperature should be changed.Also, as I understand it, the algorithm focuses on finding a proper color distribution, given the chromatic number and not on finding its value. Since there is no focus on finding the chromatic number, but rather on a coloring with cost low enough, I decided to try repurpose the algorithm by setting an upper boundary of colors via Brook's Theorem and using binary search to adjust the target cost and eventually find a solution with low enough chromatic number. This model, however, may prove slower, so I wanted to ask if you could suggest any better solutions?
Simulated Annealing for graph coloring
algorithms;graphs;heuristics