Approximate Undirected Maximum Flows in O(m polylog(n)) Time
classification
💻 cs.DS
keywords
polylogalgorithmsflowsmaximumreductionssizetimeundirected
read the original abstract
We give the first O(m polylog(n)) time algorithms for approximating maximum flows in undirected graphs and constructing polylog(n) -quality cut-approximating hierarchical tree decompositions. Our algorithm invokes existing algorithms for these two problems recursively while gradually incorporating size reductions. These size reductions are in turn obtained via ultra-sparsifiers, which are key tools in solvers for symmetric diagonally dominant (SDD) linear systems.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Flows in Almost Linear Time via Adaptive Preconditioning
Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.