Nearly maximum flows in nearly linear time

DOI10.1109/FOCS.2013.36MaRDI QIDQ6981749zbMATH OpenFDO

Authors Jonah Sherman

Publication date 20 May 2025

Full work available at URL https://doi.org/10.1109/FOCS.2013.36

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(9)

• Optimal electrical oblivious routing on expanders
• High-accuracy multicommodity flows via iterative refinement
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
• Ultrasparse ultrasparsifiers and faster Laplacian system solvers
• Maximum flow and minimum-cost flow in almost-linear time
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• Sparsification of directed graphs via cut balance
• Length-constrained directed expander decomposition and length-constrained vertex-capacitated flow shortcuts
• Acceleration meets inverse maintenance: faster _-regression

This page was built for publication: Nearly maximum flows in nearly linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6981749)