Abstract#R##N##R##N#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.
['Christian Fremuth‐Paeger', 'Dieter Jungnickel']
Balanced network flows. VII. Primal-dual algorithms