Balanced network flows. III. Strongly polynomial augmentation algorithms

From MaRDI portal





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).











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)