A spectral heuristic for bisecting random graphs

DOI10.1002/rsa.20116zbMath1111.05088OpenAlexW4252323760MaRDI QIDQ3419599

Amin Coja-Oghlan

Publication date: 7 February 2007

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20116

zbMATH Keywords

probabilistic algorithmminimum bisection

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (10)

Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Repetition-free longest common subsequence of random sequences ⋮ Message passing algorithms for MLS-3LIN problem ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ On the Laplacian Eigenvalues of G_n,p ⋮ Sparse graphs: Metrics and random models ⋮ Finding most likely solutions ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Top eigenpair statistics for weighted sparse graphs

Cites Work

• Unnamed Item

This page was built for publication: A spectral heuristic for bisecting random graphs