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

zbMATH Keywords

eigenvalueseigenvectorscomplexityapproximation algorithmline graphNP-completemax-cut

Mathematics Subject Classification ID

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)

Recommendations

• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Laplacian eigenvalues and the maximum cut problem
• scientific article; zbMATH DE number 426360
• scientific article; zbMATH DE number 780784
• Solving the max-cut problem using eigenvalues

Cited in

(32)

• Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs
• On conjectures involving second largest signless Laplacian eigenvalue of graphs
• On Khot’s unique games conjecture
• Spectral bounds for the maximum cut problem
• Null spaces of correlation matrices
• On a positive semidefinite relaxation of the cut polytope
• Use of MAX-CUT for Ramsey Arrowing of Triangles
• On computational capabilities of Ising machines based on nonlinear oscillators
• Some geometric results in semidefinite programming
• Laplacian eigenvalues and the maximum cut problem
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• A randomized approximation scheme for metric MAX-CUT
• A guide to conic optimisation and its applications
• Computational approaches to MAX-cut
• Semidefinite programming
• The Laplacian spectral radius of a graph under perturbation
• Computing the Grothendieck constant of some graph classes
• Rank of Handelman hierarchy for Max-Cut
• Diffusion bank networks and capital flows
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• \textsc{max-cut} and containment relations in graphs
• scientific article; zbMATH DE number 426360 (Why is no real title available?)
• Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems
• Combinatorial complexity of a certain 1-dimensional cutting stock problem
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• Semidefinite programming in combinatorial optimization
• A survey of automated conjectures in spectral graph theory
• Max-cut and extendability of matchings in distance-regular graphs
• Trigonometric approximation of the max-cut polytope is star-like
• New bounds for the maximum cut problem
• Solving the max-cut problem using eigenvalues
• A projection technique for partitioning the nodes of a graph

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)