Finding sparse cuts locally using evolving sets

DOI10.1145/1536414.1536449zbMath1304.05128OpenAlexW2140432232MaRDI QIDQ5172717

Reid Andersen, Yuval Peres

Publication date: 4 February 2015

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

Full work available at URL: https://doi.org/10.1145/1536414.1536449

zbMATH Keywords

graph partitioninglocal algorithmsevolving sets

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (16)

The Small Community Phenomenon in Networks: Models, Algorithms and Applications ⋮ Unnamed Item ⋮ Can we locally compute sparse connected subgraphs? ⋮ Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs ⋮ Computing heat kernel PageRank and a local clustering algorithm ⋮ Beyond good partition shapes: an analysis of diffusive graph partitioning ⋮ Reconstructing Markov processes from independent and anonymous experiments ⋮ Constructing near spanning trees with few local inspections ⋮ Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local Flow Partitioning for Faster Edge Connectivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local algorithms for sparse spanning graphs ⋮ Communities, Random Walks, and Social Sybil Defense

This page was built for publication: Finding sparse cuts locally using evolving sets