A simple version of Karzanov's blocking flow algorithm (Q795064): Difference between revisions

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. \textit{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)\) [\textit{A. V. Karzanov}, Sov. Math. Dokl. 15(1974), 434-437 (1975; Zbl 0303.90014); \textit{V. M. Malhotra, M. P. Kumar} and \textit{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.