Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
From MaRDI portal
Publication:2107015
DOI10.1007/s11128-022-03421-zOpenAlexW3125232052MaRDI QIDQ2107015
David E. Bernal, Rodolfo Quintero, Luis F. Zuluaga, Tamás Terlaky
Publication date: 29 November 2022
Published in: Quantum Information Processing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2101.09462
combinatorial optimizationquantum computingNISQ devicesChimera versus Pegasus D-wave annealerQUBO reformulations
Combinatorial optimization (90C27) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12) Other nonclassical models of computation (68Q09)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving VLSI design and DNA sequencing problems using bipartization of graphs
- The maximum \(k\)-colorable subgraph problem and orbitopes
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- The maximum k-colorable subgraph problem for chordal graphs
- QUBO formulations for the graph isomorphism problem and related problems
- A MAX-CUT formulation of 0/1 programs
- A case study in programming a quantum annealer for hard operational planning problems
- Integer programming techniques for minor-embedding in quantum annealers
- Optimal quadratic reformulations of fourth degree pseudo-Boolean functions
- On characterization of maximal independent sets via quadratic optimization
- On spectrum sharing games
- Penalty and partitioning techniques to improve performance of QUBO solvers
- A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Integer Programming
- On the Shannon capacity of a graph
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Some news about the independence number of a graph
- The approximation of maximum subgraph problems
- THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
- Relationship between minimum gap and success probability in adiabatic quantum computing
- Reducibility among Combinatorial Problems
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
- Finding independent sets in a graph using continuous multivariable polynomial formulations.