Balanced network flows. III. Strongly polynomial augmentation algorithms
For Parts I and II, see ibid. 33, 1-28, 29-41 (1999; Zbl 0999.90005 and Zbl 0999.90006). In this paper strongly polynomial augmentation algorithms for the maximum balanced flow problem are discussed. These algorithms use a double depth first search procedure. The complete balanced network search procedure finds valid augmenting paths of minimal length in linear time. Correctness and complexity are proved, and the method illustrated with an example. Next a path expanion procedure is given. The final algorithm (which is a generalization of the cardinality matching algorithm by \textit{S. Micali} and \textit{V. V. Vazirani} [An \(O(\sqrt{(V)E})\) algorithm for finding maximum matching in general graphs. Proceedings of th 21st Annual IEEE Symposium in Foundations of Computer Science, 17-27 (1980)]) computes maximum balanced flows in \(O(nm^2)\) time. For Parts IV--VII, see ibid. 37, No. 4, 194-201, 202-209, 210-218 (2001) and 39, 35-42 (2002).
- A strongly polynomial algorithm for the uniform balanced network flow problem
- Balanced network flows. IV: Duality and structure theory.
- Balanced network flows. V: Cycle-canceling algorithms.
- Balanced network flows. VI: Polyhedral descriptions.
- Balanced network flows. VII: Primal-dual algorithms.
- A POLYNOMIAL ALGORITHM FOR THE MAXIMUM BALANCED FLOW PROBLEM WITH A CONSTANT BALANCING RATE FUNCTION
- A POLYNOMIAL-TIME BINARY SEARCH ALGORITHM FOR THE MAXIMUM BALANCED FLOW PROBLEM
- Layered Augmenting Path Algorithms
- scientific article; zbMATH DE number 1769330 (Why is no real title available?)
- scientific article; zbMATH DE number 1769331 (Why is no real title available?)
- Balanced network flows. VIII. A revised theory of phase‐ordered algorithms and the O( $\bf\it\sqrt{n}m$ log(n2/m)/log n) bound for the nonbipartite cardinality matching problem
- scientific article; zbMATH DE number 842873 (Why is no real title available?)
- Balancing Applied to Maximum Network Flow Problems
- Graph factors and factorization: 1985--2003: a survey
This page was built for publication: Balanced network flows. III. Strongly polynomial augmentation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4540088)