Local Flow Partitioning for Faster Edge Connectivity
DOI10.1137/18M1180335zbMath1448.68358OpenAlexW2998970133WikidataQ126399067 ScholiaQ126399067MaRDI QIDQ5210551
Satish B. Rao, Di Wang, Monika R. Henzinger
Publication date: 21 January 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1180335
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- On clusterings
- Multi-Terminal Network Flows
- Random walks in a convex body and an improved volume algorithm
- A simple min-cut algorithm
- Local Flow Partitioning for Faster Edge Connectivity
- Deterministic Edge Connectivity in Near-Linear Time
- Finding sparse cuts locally using evolving sets
- Expander Decomposition and Pruning: Faster, Stronger, and Simpler
- Solving SDD linear systems in nearly m log 1/2 n time
- Routing under balance
- Flow-Based Algorithms for Local Graph Clustering
- A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank
- Minimum cuts in near-linear time
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Expander flows, geometric embeddings and graph partitioning
- Graph partitioning using single commodity flows
This page was built for publication: Local Flow Partitioning for Faster Edge Connectivity
