scientific article
From MaRDI portal
Publication:3137209
zbMath0792.05102MaRDI QIDQ3137209
No author found.
Publication date: 24 July 1994
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
approximation algorithmboundseigenvalue boundweighted graphLaplacian eigenvaluecut polytopeNP-completeRamanujan graphsmax- cut problemmaximum bipartite subgraphpolyhedral bound
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99)
Related Items
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, Semidefinite programming in combinatorial optimization, Graphic vertices of the metric polytope, One-third-integrality in the max-cut problem, On Laplacian spectra of parametric families of closely connected networks with application to cooperative control, Laplace eigenvalues of graphs---a survey, Sherali-adams strikes back, Unnamed Item, Tight Cycle Relaxations for the Cut Polytope, Node and edge relaxations of the max-cut problem
