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.