# Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

arXiv: https://arxiv.org/abs/2101.07233 · HTML: https://mlsanity.com/paper/2101.07233/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2021.

## Built on by (most cited first, 6 of 6)

- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Decomposable Submodular Function Minimization via Maximum Flow](https://mlsanity.com/paper/2103.03868/) (2021)
- [Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components](https://mlsanity.com/paper/2110.14859/) (2021)
- [Randomized Schur Complement Views for Graph Contrastive Learning](https://mlsanity.com/paper/2306.04004/) (2023)
- [Abstract Meaning Representation for Hospital Discharge Summarization](https://mlsanity.com/paper/2506.14101/) (2025)
- [Toward Complete Hospital Discharge Summarization with Abstract Meaning Representation](https://mlsanity.com/paper/2609.13581/) (2026)

## Abstract (arXiv)

We give an algorithm for computing exact maximum flows on graphs with m edges and integer capacities in the range [1, U] in widetildeO(m^frac32 - frac1328 log U) time. For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the widetildeO(m1.5 log U) time bound from [Goldberg-Rao JACM `98]. Our algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [Mkadry JACM `16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.