Approximate Undirected Maximum Flows in O(m polylog(n)) Time

Richard Peng

Approximate Undirected Maximum Flows in O(m polylog(n)) Time

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1411.7631 v2 pith:M2ZYUWQU submitted 2014-11-27 cs.DS

Approximate Undirected Maximum Flows in O(m polylog(n)) Time

Richard Peng This is my paper

classification cs.DS

keywords polylogalgorithmsflowsmaximumreductionssizetimeundirected

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

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.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Flows in Almost Linear Time via Adaptive Preconditioning
cs.DS 2019-06 unverdicted novelty 7.0

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.