Report Number: CS-TR-89-1248
Institution: Stanford University, Department of Computer Science
Title: Efficiency of the network simplex algorithm for the maximum
Author: Goldberg, Andrew V.
Author: Grigoriadis, Michael D.
Author: Tarjan, Robert E.
Date: February 1989
Abstract: Goldfarb and Hao have proposed a network simplex algorithm
that will solve a maximum flow problem on an n-vertex, m-arc
network in at most nm pivots and O(n2m) time. In this paper
we describe how to implement their algorithm to run in O(nm
log n) time by using an extension of the dynamic tree data
structure of Sleator and Tarjan. This bound is less than a
logarithmic factor larger than that of any other known
algorithm for the problem.