Balanced network flows. III. Strongly polynomial augmentation algorithms
Christian Fremuth‐Paeger, Dieter Jungnickel · Networks · 1999
We discuss efficient augmentation algorithms for the maximum balanced flow problem which run in O(nm2) 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. © 1999 John Wiley & Sons, Inc. Networks 33: 43–56, 1999