×

A simple version of Karzanov’s blocking flow algorithm. (English) Zbl 0542.05057

A network is a directed graph G with two distinguished vertices, a source s and a sink t, and a positive capacity c(v,w) on every edge [v,w]. A flow is blocking if there is a saturated edge on every path from s to t. E. A. Dinits [Sov. Math., Dokl. 11, 1277-1280 (1970); translation from Dokl. Akad. Nauk SSSR 194, 754-757 (1970; Zbl 0219.90046)] has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of, at most n-1 so- called ”blocking flow” problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problem is \(O(n^ 2)\) [A. V. Karzanov, Sov. Math. Dokl. 15(1974), 434-437 (1975; Zbl 0303.90014); V. M. Malhotra, M. P. Kumar and S. N. Maheshwari, Inf. Process. Lett. 7, 277-278 (1978; Zbl 0391.90041)]. In this paper the author presents a version of Karzanov’s algorithm that is easy to implement.
Reviewer: L.Caccetta

MSC:

05C99 Graph theory
68W99 Algorithms in computer science
90B10 Deterministic network models in operations research
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Cherkasky, R.V., Algorithm of construction of maximal flow in networks with complexity of O(V2√E) operations, Mathematical methods of solution of economical problems, 7, 112-125, (1977), (in Russian)
[2] Dinic, E.A., Algorithm for solution of a problem of maximum flow in a network with power estimation, Soviet math. dokl., 11, 1277-1280, (1970) · Zbl 0219.90046
[3] Even, S., Graph algorithms, (1979), Computer Science Press Potomac, MD · Zbl 0441.68072
[4] Gail, Z., An \( O(V\^{}\{53\}E\^{}\{23\})\) algorithm for the maximal flow problem, Acta informatica, 14, 221-242, (1980)
[5] Galil, Z.; Naamad, A., An O(EV log2V) algorithm for the maximal flow problem, J. computer and system sciences, 21, 203-217, (1980) · Zbl 0449.90094
[6] Karzanov, A.V., Determining the maximal flow in a network by the method of preflows, Soviet math. dokl., 15, 434-437, (1974) · Zbl 0303.90014
[7] Knuth, D.E., ()
[8] Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0358.68059
[9] Malhotra, V.M.; Kumar, M.P.; Maheshwari, S.N., An O(|V|3) algorithm for finding maximum flows in networks, (), 277-278 · Zbl 0391.90041
[10] Shiloach, Y.; Vishkin, U., An O(n2log n) parallel MAX-flow algorithm, J. algorithms, 3, 128-146, (1982) · Zbl 0483.90044
[11] Sleator, D.D., An O(nm log n) algorithm for maximum network flow, ()
[12] D.D. Sleator and R.E. Tarjan, “A data structure for dynamic trees”, J. Computer and System Sciences, to appear;
[13] Tarjan, R.E., Finding dominators in directed graphs, SIAM J. comput., 3, 62-89, (1974) · Zbl 0296.68030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.