A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time (Q750277): Difference between revisions

Given is a network with n nodes and m arcs. The authors describe the first primal simplex algorithm for the maximum flow problem which is strongly polynomial. It relies on the fact that among the variables which might enter a basis one is chosen, whose corresponding arc is closest to the source. In this case a maximum flow will be found after at most \(n\cdot m\) pivots. The authors describe also an \(O(n^ 2m)\) implementation of their new method.