Max Cut and the Smallest Eigenvalue

DOI10.1137/090773714zbMath1271.68245OpenAlexW2031481696MaRDI QIDQ4910584

Luca Trevisan

Publication date: 19 March 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090773714

zbMATH Keywords

maximum cutspectral graph theory

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Approximation algorithms (68W25)

Related Items (29)

On the bipartiteness constant and expansion of Cayley graphs ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Sharp spectral bounds of several graph parameters using eigenvector norms ⋮ Max \(k\)-cut and the smallest eigenvalue ⋮ Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology ⋮ Fast Distributed Approximation for Max-Cut ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs ⋮ A unified approach to synchronization problems over subgroups of the orthogonal group ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian ⋮ Multi-way dual Cheeger constants and spectral bounds of graphs ⋮ Simple approximation algorithms for balanced MAX~2SAT ⋮ Max-cut and extendability of matchings in distance-regular graphs ⋮ Unnamed Item ⋮ Cheeger constants, structural balance, and spectral clustering analysis for signed graphs ⋮ Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs ⋮ A spectral partitioning algorithm for maximum directed cut problem ⋮ Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians ⋮ Bipartite communities via spectral partitioning ⋮ Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem ⋮ Some observations on the smallest adjacency eigenvalue of a graph ⋮ The extreme eigenvalues and maximum degree of \(k\)-connected irregular graphs ⋮ Spectral clustering revisited: information hidden in the Fiedler vector ⋮ Unnamed Item ⋮ Combinatorial Algorithms for Minimizing the Maximum Laplacian and Signless Laplacian Eigenvalues of Weighted Graphs ⋮ The product of two high-frequency graph Laplacian eigenfunctions is smooth ⋮ Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians ⋮ Spectral distances on graphs

This page was built for publication: Max Cut and the Smallest Eigenvalue