Combinatorial properties and the complexity of a max-cut approximation

DOI10.1006/EUJC.1993.1035MaRDI QIDQ685307zbMATH OpenOpenAlexFDO

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)

• 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
• The Laplacian spectral radius of a graph under perturbation
• Semidefinite programming
• 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
• Computational approaches to MAX-cut
• 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
• Trigonometric approximation of the max-cut polytope is star-like
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• On a positive semidefinite relaxation of the cut polytope
• A randomized approximation scheme for metric MAX-CUT
• Some geometric results in semidefinite programming
• scientific article; zbMATH DE number 426360 (Why is no real title available?)
• 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)