Local Flow Partitioning for Faster Edge Connectivity

DOI10.1137/1.9781611974782.125zbMath1409.68215arXiv1704.01254OpenAlexW2951903603MaRDI QIDQ4575872

Di Wang, Satish B. Rao, Monika R. Henzinger

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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 (10)

Minimum Cuts in Surface Graphs ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Generalized cut trees for edge-connectivity ⋮ Practical Minimum Cut Algorithms ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Compact cactus representations of all non-trivial min-cuts ⋮ Local Flow Partitioning for Faster Edge Connectivity ⋮ Unnamed Item

This page was built for publication: Local Flow Partitioning for Faster Edge Connectivity