Many sparse cuts via higher eigenvalues

DOI10.1145/2213977.2214079zbMath1286.05095arXiv1111.0965OpenAlexW3098071389MaRDI QIDQ5415540

Prasad Raghavendra, Anand Louis, Prasad Tetali, Santosh Vempala

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.0965

zbMATH Keywords

graph eigenvaluesapproximation algorithmsCheeger's inequalitygraph expansionsmall-set expansion

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (10)

Spectral concentration and greedy \(k\)-clustering ⋮ Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm ⋮ Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Unnamed Item ⋮ Generalizing the hypergraph Laplacian via a diffusion process with mediators ⋮ Bipartite communities via spectral partitioning ⋮ Diffusion operator and spectral analysis for directed hypergraph Laplacian ⋮ On hyperboundedness and spectrum of Markov operators

This page was built for publication: Many sparse cuts via higher eigenvalues