scientific article; zbMATH DE number 426360

MaRDI QIDQ3137209zbMATH OpenFDO

Authors

Publication date 24 July 1994

zbMATH Keywords

approximation algorithmboundscut polytopeeigenvalue boundLaplacian eigenvaluemax- cut problemmaximum bipartite subgraphNP-completepolyhedral boundRamanujan graphsweighted graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 4193718
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Spectral bounds for the maximum cut problem
• Combinatorial properties and the complexity of a max-cut approximation
• scientific article; zbMATH DE number 780784

Cited in

(22)

• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Laplacian eigenvalues and the maximum cut problem
• Node and edge relaxations of the max-cut problem
• Semidefinite programming in combinatorial optimization
• Applications of cut polyhedra. II
• The expected relative error of the polyhedral approximation of the max- cut problem
• Solving the max-cut problem using eigenvalues
• Graphic vertices of the metric polytope
• One-third-integrality in the max-cut problem
• A class of spectral bounds for max \(k\)-cut
• Spectral bounds for the maximum cut problem
• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• Tight cycle relaxations for the cut polytope
• On Laplacian spectra of parametric families of closely connected networks with application to cooperative control
• Sherali-adams strikes back
• Sherali-Adams strikes back
• scientific article; zbMATH DE number 4193718 (Why is no real title available?)
• Algorithms – ESA 2005
• Combinatorial properties and the complexity of a max-cut approximation
• Laplace eigenvalues of graphs---a survey
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Canonical dual approach to solving the maximum cut problem

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 Q3137209)