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

Balanced network flows. III. Strongly polynomial augmentation algorithms

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

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

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 matching algorithm given by Micali and Vazirani. A comprehensive description of the double depth first search is included.

๐Ÿ“œ 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. 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