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

DOI10.7468/JKSMEB.2024.31.1.57MaRDI QIDQ6546089zbMATHFDO

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)

zbMATH Keywords

graph coloringdegree reductionquantum annealingQUBO

Mathematics Subject Classification ID

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

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

Cites work

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

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)