[1] For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available.
[3] Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.
At each iteration, an entering variable is selected by some pricing strategy, based on the dual multipliers (node potentials), and forms a cycle with the arcs of the tree.
The substitution of entering for leaving arc, and the reconstruction of the tree is called a pivot.
When no non-basic arc remains eligible to enter, the optimal solution has been reached.