Computing maximum flow with augmenting electrical flows

DOI10.1109/FOCS.2016.70MaRDI QIDQ6946438zbMATH OpenFDO

Authors Aleksander Mądry

Publication date 6 August 2025

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx)

Cited in

(9)

• Faster algorithms for rooted connectivity in directed graphs
• Isolating cuts, (bi-)submodularity, and faster algorithms for connectivity
• Deterministic maximum flows in simple graphs
• Minimum cut in O(m^2 n time
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
• High-accuracy multicommodity flows via iterative refinement
• Electrical flows for polylogarithmic competitive oblivious routing
• Negative-weight single-source shortest paths in near-linear time
• Maximum flow and minimum-cost flow in almost-linear time

This page was built for publication: Computing maximum flow with augmenting electrical flows

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