A Note on Cut-Approximators and Approximating Undirected Max Flows.
Richard Peng · arXiv (Cornell University) · 2014
We show a closer algorithmic connection between constructing cut-approximating hierarchical tree decompositions and computing approximate maximum flows in undirected graphs. This leads to the first O(m polylog(n)) time algorithms for both problems.