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-IzbMath0786.05057MaRDI QIDQ686456
Charles Delorme, Svatopluk Poljak
Publication date: 20 December 1993
Published in: Discrete Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs, On a positive semidefinite relaxation of the cut polytope, Solving the max-cut problem using eigenvalues, A survey of graph laplacians, Computing the Grothendieck constant of some graph classes, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, Simplicial faces of the set of correlation matrices, Max-cut and extendability of matchings in distance-regular graphs, Laplace eigenvalues of graphs---a survey, A survey of automated conjectures in spectral graph theory, On conjectures involving second largest signless Laplacian eigenvalue of graphs, The Laplacian spectral radius of a graph under perturbation, Spectral partitioning with multiple eigenvectors, Scalable Semidefinite Programming, Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT, Laplacian eigenvalues and the maximum cut problem
Cites Work
- On some weakly bipartite graphs
- On a pair of dual subschemes of the Hamming scheme \(H_ n(q)\)
- Weakly bipartite graphs and the max-cut problem
- Compositions in the bipartite subgraph polytope
- Laplacian eigenvalues and the maximum cut problem
- On Transportation Problems with Upper Bounds on Leading Rectangles
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Lower Bounds for the Partitioning of Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
