Characterization of QUBO reformulations for the maximum k-colorable subgraph problem
DOI10.1007/S11128-022-03421-ZOpenAlexW3125232052MaRDI QIDQ2107015FDOQ2107015
Authors: Rodolfo Quintero, David E. Bernal, Luis Fernando 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
Recommendations
- Penalty and partitioning techniques to improve performance of QUBO solvers
- Reformulating the harmonious colouring problem for quantum annealing
- Quantum solutions for densest \(k\)-subgraph problems
- QUBO formulations for the graph isomorphism problem and related problems
- Modeling the Costas array problem in QUBO for quantum annealing
combinatorial optimizationquantum computingChimera versus Pegasus D-wave annealerNISQ devicesQUBO reformulations
Combinatorial optimization (90C27) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Other nonclassical models of computation (68Q09)
Cites Work
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
- On the Shannon capacity of a graph
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Title not available (Why is that?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- The maximum \(k\)-colorable subgraph problem and orbitopes
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- The maximum k-colorable subgraph problem for chordal graphs
- Title not available (Why is that?)
- A case study in programming a quantum annealer for hard operational planning problems
- On characterization of maximal independent sets via quadratic optimization
- Solving VLSI design and DNA sequencing problems using bipartization of graphs
- The approximation of maximum subgraph problems
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Finding independent sets in a graph using continuous multivariable polynomial formulations.
- Relationship between minimum gap and success probability in adiabatic quantum computing
- On spectrum sharing games
- Integer Programming
- QUBO formulations for the graph isomorphism problem and related problems
- A MAX-CUT formulation of 0/1 programs
- Some news about the independence number of a graph
- A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
- Integer programming techniques for minor-embedding in quantum annealers
- Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
- Optimal quadratic reformulations of fourth degree pseudo-Boolean functions
- Penalty and partitioning techniques to improve performance of QUBO solvers
- THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
Cited In (8)
- Quantum solutions for densest \(k\)-subgraph problems
- Solving the Kemeny ranking aggregation problem with quantum optimization algorithms
- Penalty and partitioning techniques to improve performance of QUBO solvers
- Characterization of QUBO reformulations for the maximum $k$-colorable subgraph problem
- Reformulating the harmonious colouring problem for quantum annealing
- The set partitioning problem in a quantum context
- QUBO formulations of the longest path problem
- A copositive framework for analysis of hybrid Ising-classical algorithms
This page was built for publication: Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2107015)
