Quantum annealing of the graph coloring problem

DOI10.1016/j.disopt.2010.12.001zbMath1244.05097MaRDI QIDQ429697

Olawale Titiloye, Alan Crispin

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.12.001

zbMATH Keywords

combinatorial optimization; simulated annealing; quantum annealing; graph coloring problem

Mathematics Subject Classification ID

90C27: Combinatorial optimization

05C15: Coloring of graphs and hypergraphs

Related Items

Primal Heuristics for Branch and Price: The Assets of Diving Methods, An exact algorithm with learning for the graph coloring problem, Improving the extraction and expansion method for large graph coloring, Large-scale vehicle routing problems: quantum annealing, tunings and results, Maximum-weight stable sets and safe lower bounds for graph coloring, An improved noise quantum annealing method for TSP, A systematic study on meta-heuristic approaches for solving the graph coloring problem, AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING, Safe Lower Bounds for Graph Coloring

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Using tabu search techniques for graph coloring
• Some experiments with simulated annealing for coloring graphs
• An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring
• A memetic algorithm for graph coloring
• Hybrid evolutionary algorithms for graph coloring
• A graph coloring heuristic using partial solutions and a reactive tabu scheme
• An adaptive memory algorithm for the \(k\)-coloring problem
• A survey of local search methods for graph coloring
• Relationship between d-Dimensional Quantal Spin Systems and (d+1)-Dimensional Ising Systems: Equivalence, Critical Exponents and Systematic Approximants of the Partition Function and Spin Correlations
• A Metaheuristic Approach for the Vertex Coloring Problem
• Colloquium: Quantum annealing and analog quantum computation
• On the Product of Semi-Groups of Operators
• A graph coloring algorithm for large scheduling problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• A Pruning Procedure for Exact Graph Coloring
• The Complexity of Near-Optimal Graph Coloring