Report Number: CS-TR-78-702
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