Institution: Stanford University, Department of Computer Science

Title: An O($n\cdot I \log^2 I$) maximum-flow algorithm

Author: Shiloach, Yossi

Date: December 1978

Abstract: We present in this paper a new algorithm to find a maximum flow in a flow-network which has n vertices and m edges in time of O($n\cdot I \log^2 I$), where I = M+n is the input size (up to a constant factor). This result improves the previous upper bound of Z . Galil [1978] which was O($I^{7/3}$) in the worst case.

http://i.stanford.edu/pub/cstr/reports/cs/tr/78/702/CS-TR-78-702.pdf