𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Balanced network flows. VII. Primal-dual algorithms

✍ Scribed by Christian Fremuth-Paeger; Dieter Jungnickel

Publisher
John Wiley and Sons
Year
2001
Tongue
English
Weight
559 KB
Volume
39
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Balanced network flows. II. Simple augme
Balanced network flows. II. Simple augmentation algorithms
✍ Fremuth-Paeger, Christian; Jungnickel, Dieter πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 165 KB

In previous papers, we discussed the fundamental theory of matching problems and algorithms in terms of a network flow model. In this paper, we present explicit augmentation procedures which apply to the wide range of capacitated matching problems and which are highly efficient for k-factor problems

Balanced network flows. III. Strongly po
Balanced network flows. III. Strongly polynomial augmentation algorithms
✍ Fremuth-Paeger, Christian; Jungnickel, Dieter πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 162 KB

We discuss efficient augmentation algorithms for the maximum balanced flow problem which run in O(nm 2 ) 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 match

Balanced network flows. I. A unifying fr
Balanced network flows. I. A unifying framework for design and analysis of matching algorithms
✍ Fremuth-Paeger, Christian; Jungnickel, Dieter πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 418 KB πŸ‘ 2 views

We discuss a wide range of matching problems in terms of a network flow model. More than this, we start up a matching theory which is very intuitive and independent from the original graph context. This first paper contains a standardized theory for the performance analysis of augmentation algorithm