Simulated Annealing Algorithm for Graph Coloring
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 \(\mathbf{H}\) by varying the parameters like \(\mathbf{q}\) (Number of colors that can be used in coloring) and \(\mathbf{c}\) (Average node degree). The results are obtained by using simulated annealing scheme, where the temperature (inverse of \(\mathbf{\beta}\)) parameter in the MCMC is lowered progressively.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Estudo comparativo de meta-heurísticas para problemas de colorações de grafos
A classic graph coloring problem is to assign colors to vertices of any graph so that distinct colors are assigned to adjacent vertices. Optimal graph coloring colors a graph with a minimum number of colors, which is its…
Combinatorial OptimizationVariations on Memetic Algorithms for Graph Coloring Problems
Graph vertex coloring with a given number of colors is a well-known and much-studied NP-complete problem.The most effective methods to solve this problem are proved to be hybrid algorithms such as memetic algorithms or q…
DiversityAn Upper Bound for Minimum True Matches in Graph Isomorphism with Simulated Annealing
Graph matching is one of the most important problems in graph theory and combinatorial optimization, with many applications in various domains. Although meta-heuristic algorithms have had good performance on many NP-Hard…
Combinatorial OptimizationGraph MatchingStochastic OptimizationLearning Complexity of Simulated Annealing
Simulated annealing is an effective and general means of optimization. It is in fact inspired by metallurgy, where the temperature of a material determines its behavior in thermodynamics. Likewise, in simulated annealing…
A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time with respect to the logarithm of the size of the state space. This is the first speed-up of this type to be obtained over th…