scientific article; zbMATH DE number 780784
From MaRDI portal
Publication:4840774
bipartite subgraphcomplexityconvex hullcryptogramscutcut polytopeeigenvaluefacetsinequalitiesIsing modelsLaplacianlocal searchmetric polytopepartitionplanar graphspolyhedral theorypolynomially solvableprogrammingsigned graphsspinVLSI design
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Extremal problems in graph theory (05C35) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Recommendations
Cited in
(82)- The Laplacian spectral radius of a graph under perturbation
- Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
- Compositions in the bipartite subgraph polytope
- On a bottleneck bipartition conjecture of Erdős
- Max-cut in circulant graphs
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
- The line index and minimum cut of weighted graphs
- Maximum cut on line and total graphs
- Semidefinite programming in combinatorial optimization
- Cuts, matrix completions and graph rigidity
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Easy and difficult objective functions for max cut
- The maximum cardinality cut problem in co-bipartite chain graphs
- A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
- On graphs of the cone decompositions for the min-cut and max-cut problems
- Programming for modular reconfigurable robots
- One-third-integrality in the max-cut problem
- A study of the performance of classical minimizers in the quantum approximate optimization algorithm
- Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
- Cuts in undirected graphs. I
- Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
- Hypergraph cuts above the average
- Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs
- Large cuts with local algorithms on triangle-free graphs
- Approximation algorithms for maximum cut with limited unbalance
- Approximating the fixed linear crossing number
- A counterexample to the dominating set conjecture
- An exact algorithm for MAX-CUT in sparse graphs
- A semidefinite programming based polyhedral cut and price approach for the maxcut problem
- A \(2^{|E|/4}\)-time algorithm for MAX-CUT
- Computing the largest bond and the maximum connected cut of a graph
- SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
- An effective compact formulation of the max cut problem on sparse graphs
- Judicious bisection of hypergraphs
- Settling the complexity of local max-cut (almost) completely
- Computational experience with a SDP-based algorithm for maximum cut with limited unbalance
- The maximum cut problem
- scientific article; zbMATH DE number 426360 (Why is no real title available?)
- Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors
- Sequences of radius \(k\) for complete bipartite graphs
- A polynomial algorithm for the max-cut problem on graphs without long odd cycles
- New bounds for the maximum cut problem
- Spectral bounds for the maximum cut problem
- On judicious bisections of graphs
- Lifting and separation procedures for the cut polytope
- scientific article; zbMATH DE number 176747 (Why is no real title available?)
- On the Maximum Cut of Line Graphs
- Linear-Time Approximation Algorithms for the Max Cut Problem
- Partitioning planar graphs: a fast combinatorial approach for max-cut
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- Online maximum directed cut
- scientific article; zbMATH DE number 1787231 (Why is no real title available?)
- Solving the maxcut problem by the global equilibrium search
- scientific article; zbMATH DE number 1833086 (Why is no real title available?)
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Bounds for the Laplacian spectral radius of graphs
- The complexity of SIMPLE MAX-CUT on comparability graphs
- Sequences of radius \(k\) for complete bipartite graphs
- Semidefinite programming and combinatorial optimization
- MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems
- On the bond polytope
- Algorithm unions for solving discrete optimization problems
- Small bipartite subgraph polytopes
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
- On skeletons, diameters and volumes of metric polyhedra
- An experimental evaluation of semidefinite programming and spectral algorithms for max cut
- Counting connected partitions of graphs
- Canonical cuts of path powers
- The real positive semidefinite completion problem for series-parallel graphs
- Combinatorial properties and the complexity of a max-cut approximation
- Dual Cheeger constants, signless 1-Laplacians and maxcut
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
- On cut polytopes and graph minors
- Linear kernels and linear-time algorithms for finding large cuts
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
- Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity
- Partitioning 3-uniform hypergraphs
- Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\)
- A survey of automated conjectures in spectral graph theory
- Maximum cut in fuzzy nature: models and algorithms
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4840774)
