Unit capacity maxflow in almost O(m^4/3) time

DOI10.1109/FOCS46700.2020.00020MaRDI QIDQ6944037zbMATH OpenFDO

Authors Tarun Kathuria, Yang P. Liu, Aaron Sidford

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00020

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35) Interior-point methods (90C51)

Cited in

(9)

• High-accuracy multicommodity flows via iterative refinement
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
• Maximum flow and minimum-cost flow in almost-linear time
• Fast algorithms for _p-regression
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• Faster algorithms for rooted connectivity in directed graphs
• Isolating cuts, (bi-)submodularity, and faster algorithms for connectivity
• AC(k): robust solution of Laplacian equations by randomized approximate Cholesky factorization
• Connectivity-preserving minimum separator in AT-free graphs

This page was built for publication: Unit capacity maxflow in almost \(O(m^{4/3})\) time

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