Complexity and Polynomially Solvable Special Cases of QUBO
From MaRDI portal
Publication:5050143
DOI10.1007/978-3-031-04520-2_3zbMath1506.90191OpenAlexW4285030499MaRDI QIDQ5050143
Eranda Çela, Abraham P. Punnen
Publication date: 15 November 2022
Published in: The Quadratic Unconstrained Binary Optimization Problem (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-04520-2_3
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The clique problem in ray intersection graphs
- The unconstrained binary quadratic programming problem: a survey
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Partitioning planar graphs: a fast combinatorial approach for max-cut
- On duality gap in binary quadratic programming
- NP-hardness of the Euclidean Max-Cut problem
- The max-cut problem on graphs not contractible to \(K_ 5\)
- A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems
- The Wiener maximum quadratic assignment problem
- Maximum independent sets in 3- and 4-regular Hamiltonian graphs
- Maximum weight independent sets in hole- and dart-free graphs
- A survey for the quadratic assignment problem
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Optimal cuts in graphs and statistical mechanics
- Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem
- Decomposition by clique separators
- A solvable case of quadratic 0-1 programming
- Weakly bipartite graphs and the max-cut problem
- Unit disk graphs
- Computing independent sets in graphs with large girth
- Optimization, approximation, and complexity classes
- A solvable class of quadratic 0-1 programming
- The max clique problem in classes of string-graphs
- Geometric algorithms and combinatorial optimization
- Some simplified NP-complete graph problems
- A partial k-arboretum of graphs with bounded treewidth
- The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
- Maximum cut on line and total graphs
- The maximum clique problem
- The quadratic assignment problem. Theory and algorithms
- A tribute to Frank Harary (in honor of his 70th birthday)
- Easy and difficult objective functions for max cut
- Diameter and treewidth in minor-closed graph families
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- The generalized vertex cover problem and some variations
- Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
- New results on the completion time variance minimization
- A new polynomially solvable class of quadratic optimization problems with box constraints
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
- An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
- The basic algorithm for pseudo-Boolean programming revisited
- An improved fixed-parameter algorithm for max-cut parameterized by crossing number
- Well-solvable cases of the QAP with block-structured matrices
- The maximum clique problem in multiple interval graphs
- Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Tape bounds for time-bounded Turing machines
- Graph separation techniques for quadratic zero-one programming
- Minimization of Half-Products
- On the practically interesting instances of MAXCUT
- Polynomially Solvable Cases of Binary Quadratic Programs
- Maximizing the Product of Two Linear Functions In 0-1 Variables
- Assignment Problems and the Location of Economic Activities
- A polynomial algorithm for the max-cut problem on graphs without long odd cycles
- Assignment Problems
- Multi-Terminal Network Flows
- A Separator Theorem for Planar Graphs
- On the complexity of integer programming
- Selected Applications of Minimum Cuts in Networks
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Minimum cuts and related problems
- A New Algorithm for Generating All the Maximal Independent Sets
- Space bounds for a game on graphs
- Maximum Cut Parameterized by Crossing Number
- Numerical Linear Algebra and Matrix Factorizations
- Unifying maximum cut and minimum cut of a planar graph
- Node-and edge-deletion NP-complete problems
- Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
- Nested Dissection of a Regular Finite Element Mesh
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Algorithms - ESA 2003
- Optimization via enumeration: A new algorithm for the max cut problem
- A polynomial case of unconstrained zero-one quadratic optimization
- Algorithms for minclique scheduling problems
