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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.