Efficiency of the Network Simplex Algorithm for the Maximum Flow Problem
PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 On squared m time. In this paper we describe how to implement their algorithm to run in Onmlog 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. Keywords Algorithms Complexity Data structures Dynamic trees Graphs Linear programming Maximum flow Network flow Network optimization.
- Operations Research