A degree reduction method for an efficient QUBO formulation for the graph coloring problem

DOI10.7468/JKSMEB.2024.31.1.57zbMATH Open1541.05064MaRDI QIDQ6546089FDOQ6546089

Authors: Hyosang Kang, Hyunwoo Jung, Chaehwan Seol, Namho Hong, Hyunjin Lim, Seokhyun Um 

Publication date: 29 May 2024

Published in: Journal of the Korean Society of Mathematical Education. Series B. The Pure and Applied Mathematics (Search for Journal in Brave)

Recommendations

• Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems
• Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis
• Quadratic reformulations of nonlinear binary optimization problems
• QUBO formulations for the graph isomorphism problem and related problems
• Reformulating the harmonious colouring problem for quantum annealing

zbMATH Keywords

graph coloringdegree reductionquantum annealingQUBO

Mathematics Subject Classification ID

Quantum computation (81P68) Coloring of graphs and hypergraphs (05C15) General binary quadratic forms (11E16)

Cites Work

• Some simplified NP-complete graph problems
• A graph coloring algorithm for large scheduling problems
• Quantum stochastic optimization
• Minimizing minor embedding energy: an application in quantum annealing

This page was built for publication: A degree reduction method for an efficient QUBO formulation for the graph coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6546089)