The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
From MaRDI portal
Publication:686456
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)
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
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35)
Cites Work
- Graph theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Laplacian eigenvalues and the maximum cut problem
- Title not available (Why is that?)
- Lower Bounds for the Partitioning of Graphs
- Weakly bipartite graphs and the max-cut problem
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Title not available (Why is that?)
- On Transportation Problems with Upper Bounds on Leading Rectangles
- Compositions in the bipartite subgraph polytope
- Title not available (Why is that?)
- On a pair of dual subschemes of the Hamming scheme \(H_ n(q)\)
- On some weakly bipartite graphs
Cited In (21)
- Spectral bounds for the maximum cut problem
- Computing the Grothendieck constant of some graph classes
- Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
- The Laplacian spectral radius of a graph under perturbation
- Solving the max-cut problem using eigenvalues
- Combinatorial properties and the complexity of a max-cut approximation
- On conjectures involving second largest signless Laplacian eigenvalue of graphs
- Simplicial faces of the set of correlation matrices
- Spectral partitioning with multiple eigenvectors
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- Scalable Semidefinite Programming
- Laplace eigenvalues of graphs---a survey
- Laplacian eigenvalues and the maximum cut problem
- On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem
- A survey of graph laplacians
- On a positive semidefinite relaxation of the cut polytope
- Title not available (Why is that?)
- Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs
- 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: 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)
