Four proofs for the Cheeger inequality and graph partition algorithms

zbMATH Open1210.05076MaRDI QIDQ3078044FDOQ3078044

Authors: Fan Chung 

Publication date: 18 February 2011

Recommendations

• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
• A local graph partitioning algorithm using heat kernel pagerank
• A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank

zbMATH Keywords

Laplacianrandom walksheat kernelPageRankCheeger inequalitiesDirichlet eigenvaluesgraph partition algorithms

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10)

Cited In (6)

• Normalized Laplacian eigenvalues of hypergraphs
• Finding and using expanders in locally sparse graphs
• A global Poincaré inequality on graphs via a conical curvature-dimension condition
• On the bipartiteness constant and expansion of Cayley graphs
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile

This page was built for publication: Four proofs for the Cheeger inequality and graph partition algorithms

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