From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

Daniel Dadush, James B. Orlin, Aaron Sidford +1

We provide faster strongly polynomial time algorithms solving maximum flow in structured $n$-node $m$-arc networks. Our results imply an $n^{\omega +o(1)}$-time strongly polynomial time…