Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow
We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m1+o(1) time.