Balanced network flows. III. Strongly polynomial augmentation algorithms

We discuss efficient augmentation algorithms for the maximum balanced flow problem which run in O(nm²) time. More explicitly, we discuss a balanced network search procedure which finds valid augmenting paths of minimum length in linear time. The algorithms are based on the famous cardinality matching algorithm given by Micali and Vazirani. A comprehensive description of the double depth first search is included.