An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations.

Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford

Browse the full SODA paper archive.