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

Tarjan, Robert Endre

Oper. Res. Lett. 2, 265-268 (1984).

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

Keywords:

graph algorithm; maximum flow problem

Citations:

Zbl 0219.90046; Zbl 0303.90014; Zbl 0391.90041

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