Four proofs for the Cheeger inequality and graph partition algorithms

MaRDI QIDQ3078044zbMATH OpenFDO

Authors Fan Chung

Publication date 18 February 2011

zbMATH Keywords

Cheeger inequalitiesDirichlet eigenvaluesgraph partition algorithmsheat kernelLaplacianPageRankrandom walks

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

(10)

• 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
• Finding and using expanders in locally sparse graphs
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Normalized Laplacian eigenvalues of hypergraphs
• Isoperimetric profile and resistance diameters of Cayley graphs on symmetric groups with Coxeter generating sets
• A note on Cheeger inequalities for uniform hypergraphs
• Supersymmetry breaking in graph quantum mechanics
• Title not available (Why is no real title available?)

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)