The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

DOI10.1016/0012-365X(93)90151-IzbMATH Open0786.05057MaRDI QIDQ686456FDOQ686456

Authors C. Delorme, Svatopluk Poljak 

Publication date 20 December 1993

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

eigenvaluesLaplacian matrixmaximum cut problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35)

Recommendations

• On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem
• scientific article; zbMATH DE number 4193718
• scientific article; zbMATH DE number 426360
• A class of spectral bounds for max \(k\)-cut
• Max \(k\)-cut and the smallest eigenvalue
• Spectral bounds for the maximum cut problem
• On the approximability of Max-Cut
• Bounds on the eigenvalues of graphs with cut vertices or edges
• Bound on the least eigenvalue of a graph with cut vertices
• Improved approximation of Max-Cut on graphs of bounded degree

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 51950 (Why is no real title available?)
• scientific article; zbMATH DE number 4193718 (Why is no real title available?)
• scientific article; zbMATH DE number 3296351 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• Compositions in the bipartite subgraph polytope
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Graph theory
• Laplacian eigenvalues and the maximum cut problem
• Lower Bounds for the Partitioning of Graphs
• On Transportation Problems with Upper Bounds on Leading Rectangles
• On a pair of dual subschemes of the Hamming scheme \(H_ n(q)\)
• On some weakly bipartite graphs
• Weakly bipartite graphs and the max-cut problem

Cited in

(23)

• Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
• Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs
• On conjectures involving second largest signless Laplacian eigenvalue of graphs
• Spectral bounds for the maximum cut problem
• On a positive semidefinite relaxation of the cut polytope
• Laplacian eigenvalues and the maximum cut problem
• Simplicial faces of the set of correlation matrices
• A survey of graph laplacians
• Sharp spectral bounds of several graph parameters using eigenvector norms
• Scalable semidefinite programming
• Spectral partitioning with multiple eigenvectors
• Combinatorial properties and the complexity of a max-cut approximation
• The Laplacian spectral radius of a graph under perturbation
• Computing the Grothendieck constant of some graph classes
• scientific article; zbMATH DE number 426360 (Why is no real title available?)
• On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem
• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
• Laplace eigenvalues of graphs---a survey
• A class of spectral bounds for max \(k\)-cut
• A survey of automated conjectures in spectral graph theory
• Max-cut and extendability of matchings in distance-regular graphs
• New bounds for the maximum cut problem
• Solving the max-cut problem using eigenvalues

This page was built for publication: The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686456)