Four proofs for the Cheeger inequality and graph partition algorithms

MaRDI QIDQ3078044zbMATHFDO

Authors Fan Chung

Publication date 18 February 2011

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)

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

Cited in

(6)

• 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
• Normalized Laplacian eigenvalues of hypergraphs
• 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)