Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

Aaron Bernstein, Joakim Blikstad, Jason Li +2

We give a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\{1,\dots ,U\}$ in $\tilde{O}(n^2\log U)$ time,…