An Adaptive Spectral Heuristic for Partitioning Random Graphs

DOI10.1007/11786986_60MaRDI QIDQ3613801zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_60

zbMATH Keywords

graph partition problemrandom input graphspectral algorithm

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Graph partitioning via adaptive spectral techniques
• A spectral heuristic for bisecting random graphs
• A simple spectral algorithm for recovering planted partitions
• Fundamentals of Computation Theory
• A spectral heuristic for bisecting random graphs

Cited in

(7)

• Separating populations with wide data: a spectral analysis
• A spectral heuristic for bisecting random graphs
• scientific article; zbMATH DE number 3855168 (Why is no real title available?)
• Graph partitioning via adaptive spectral techniques
• New abilities and limitations of spectral graph bisection
• A Spectral Method for MAX2SAT in the Planted Solution Model
• Algorithms and Computation

This page was built for publication: An Adaptive Spectral Heuristic for Partitioning Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613801)