Balanced network flows. VII. Primal‐dual algorithms
Christian Fremuth‐Paeger, Dieter Jungnickel · Networks · 2001
Abstract We discuss an adaptation of the famous primal‐dual 1‐matching algorithm to balanced network flows which can be viewed as a network flow description of capacitated matching problems. This method is endowed with a sophisticated start‐up procedure which eventually makes the algorithm strongly polynomial. We apply the primal‐dual algorithm to the shortest valid path problem with arbitrary arc lengths, and so end up with a new complexity bound for this problem. © 2002 John Wiley & Sons, Inc.