Simulated Annealing Algorithm for Graph Coloring

2017/12/03 by Alper Köse, Alper Kose, Berke Aral Sonmez +4 · 1 citation
Computer Science · Decision Sciences · Engineering · #Constraint Satisfaction and Optimization #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods #cs.AI

paper · pdf · doi:10.48550/arxiv.1712.00709

arxiv created 2017/12/03 · arxiv updated 2017/12/05

Abstract

The goal of this Random Walks project is to code and experiment the Markov Chain Monte Carlo (MCMC) method for the problem of graph coloring. In this report, we present the plots of cost function \(H\) by varying the parameters like \(q\) (Number of colors that can be used in coloring) and \(c\) (Average node degree). The results are obtained by using simulated annealing scheme, where the temperature (inverse of \(\mathbfβ\)) parameter in the MCMC is lowered progressively.

Cited by

• Wave Function Collapse Coloring: A New Heuristic for Fast Vertex Coloring

Related

• A fresh look to a randomized massively parallel graph coloring algorithm
• Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring
• Graph colouring algorithms
• A simple algorithm for sampling colourings of G(n,d/n) up to Gibbs Uniqueness Threshold
• Improved Distributed Algorithms for Random Colorings