๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Balanced network flows. II. Simple augmentation algorithms

โœ Scribed by Fremuth-Paeger, Christian; Jungnickel, Dieter

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
165 KB
Volume
33
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 and the f-factor problem.

๐Ÿ“œ SIMILAR VOLUMES

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