Complexity and Polynomially Solvable Special Cases of QUBO (Q5050143)

scientific article; zbMATH DE number 7616611

Language	Label	Description	Also known as
English	Complexity and Polynomially Solvable Special Cases of QUBO	scientific article; zbMATH DE number 7616611

Statements

instance of

scholarly article

0 references

title

Complexity and Polynomially Solvable Special Cases of QUBO (English)

0 references

0 references

0 references

The Quadratic Unconstrained Binary Optimization Problem

0 references

publication date

15 November 2022

0 references

zbMATH Keywords

computational complexity aspects

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-031-04520-2_3

0 references

cites work

NP-hardness of the Euclidean Max-Cut problem

0 references

A polynomial case of unconstrained zero-one quadratic optimization

0 references

Optimal cuts in graphs and statistical mechanics

0 references

Minimization of Half-Products

0 references

The max-cut problem on graphs not contractible to \(K_ 5\)

0 references

A solvable case of quadratic 0-1 programming

0 references

Maximum weight independent sets in hole- and dart-free graphs

0 references

A tribute to Frank Harary (in honor of his 70th birthday)

0 references

A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems

0 references

Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem

0 references

On the practically interesting instances of MAXCUT

0 references

Q4471358

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

Q4500843

0 references

Q3145799

0 references

On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem

0 references

Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences

0 references

The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases

0 references

Assignment Problems

0 references

The clique problem in ray intersection graphs

0 references

The quadratic assignment problem. Theory and algorithms

0 references

Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

0 references

The Wiener maximum quadratic assignment problem

0 references

Well-solvable cases of the QAP with block-structured matrices

0 references

A solvable class of quadratic 0-1 programming

0 references

Maximum Cut Parameterized by Crossing Number

0 references

Unit disk graphs

0 references

The basic algorithm for pseudo-Boolean programming revisited

0 references

Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs

0 references

MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs

0 references

Q3772828

0 references

Diameter and treewidth in minor-closed graph families

0 references

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

0 references

Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm

0 references

Maximum independent sets in 3- and 4-regular Hamiltonian graphs

0 references

The maximum clique problem in multiple interval graphs

0 references

Optimization via enumeration: A new algorithm for the max cut problem

0 references

Q4198056

0 references

Some simplified NP-complete graph problems

0 references

Algorithms for a maximum clique and a maximum independent set of a circle graph

0 references

Nested Dissection of a Regular Finite Element Mesh

0 references

Multi-Terminal Network Flows

0 references

A polynomial algorithm for the max-cut problem on graphs without long odd cycles

0 references

Weakly bipartite graphs and the max-cut problem

0 references

Q3216686

0 references

Geometric algorithms and combinatorial optimization

0 references

Maximum cut on line and total graphs

0 references

Finding a Maximum Cut of a Planar Graph in Polynomial Time

0 references

Maximizing the Product of Two Linear Functions In 0-1 Variables

0 references

Algorithms - ESA 2003

0 references

A new polynomially solvable class of quadratic optimization problems with box constraints

0 references

Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

0 references

Algorithms for minclique scheduling problems

0 references

An improved fixed-parameter algorithm for max-cut parameterized by crossing number

0 references

The unconstrained binary quadratic programming problem: a survey

0 references

Assignment Problems and the Location of Economic Activities

0 references

Q3348944

0 references

New results on the completion time variance minimization

0 references

Polynomially Solvable Cases of Binary Quadratic Programs

0 references

Partitioning planar graphs: a fast combinatorial approach for max-cut

0 references

A Separator Theorem for Planar Graphs

0 references

A survey for the quadratic assignment problem

0 references

Numerical Linear Algebra and Matrix Factorizations

0 references

Easy and difficult objective functions for max cut

0 references

The max clique problem in classes of string-graphs

0 references

Computing independent sets in graphs with large girth

0 references

An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs

0 references

The generalized vertex cover problem and some variations

0 references

On the complexity of integer programming

0 references

Optimization, approximation, and complexity classes

0 references

Graph separation techniques for quadratic zero-one programming

0 references

The maximum clique problem

0 references

Tape bounds for time-bounded Turing machines

0 references

Space bounds for a game on graphs

0 references

Selected Applications of Minimum Cuts in Networks

0 references

Minimum cuts and related problems

0 references

Q4770411

0 references

Unifying maximum cut and minimum cut of a planar graph

0 references

On duality gap in binary quadratic programming

0 references

Decomposition by clique separators

0 references

A New Algorithm for Generating All the Maximal Independent Sets

0 references

Node-and edge-deletion NP-complete problems

0 references

Identifiers

zbMATH Open document ID

1506.90191

0 references

DOI

10.1007/978-3-031-04520-2_3

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5050143