We show how to use tree clustering techniques to improve the time bounds for optimal pivot selection in the primal network simplex algorithm for minimum cost flow, and for pivot execution in the dual network simplex algorithm for the same problem, from O(m) to O([square root of]m) per pivot. Our techniques can also speed up network simplex algorithms for generalized flow, shortest paths with negative edges, maximum flow, the assignment problem, and the transshipment problem.
