Combinatorial properties and the complexity of a max-cut approximation
DOI10.1006/EUJC.1993.1035zbMATH Open0780.05040OpenAlexW2014079391MaRDI QIDQ685307FDOQ685307
Authors: C. Delorme, Svatopluk Poljak 
Publication date: 5 December 1993
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/eujc.1993.1035
Recommendations
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Cited In (30)
- Use of MAX-CUT for Ramsey Arrowing of Triangles
- Combinatorial complexity of a certain 1-dimensional cutting stock problem
- Spectral bounds for the maximum cut problem
- Null spaces of correlation matrices
- Computing the Grothendieck constant of some graph classes
- Rank of Handelman hierarchy for Max-Cut
- Semidefinite programming
- The Laplacian spectral radius of a graph under perturbation
- Solving the max-cut problem using eigenvalues
- A projection technique for partitioning the nodes of a graph
- Diffusion bank networks and capital flows
- On Khot’s unique games conjecture
- On conjectures involving second largest signless Laplacian eigenvalue of graphs
- A guide to conic optimisation and its applications
- Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
- \textsc{max-cut} and containment relations in graphs
- Semidefinite programming in combinatorial optimization
- Laplacian eigenvalues and the maximum cut problem
- On computational capabilities of Ising machines based on nonlinear oscillators
- Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
- On a positive semidefinite relaxation of the cut polytope
- Some geometric results in semidefinite programming
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- A randomized approximation scheme for metric MAX-CUT
- Title not available (Why is that?)
- Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs
- Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems
- New bounds for the maximum cut problem
- A survey of automated conjectures in spectral graph theory
- Max-cut and extendability of matchings in distance-regular graphs
This page was built for publication: Combinatorial properties and the complexity of a max-cut approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685307)
