A simple version of Karzanov's blocking flow algorithm
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.
- An \(O(EV\log^2V)\) algorithm for the maximal flow problem
- An \(O(IVI^3)\) algorithm for finding maximum flows in networks
- An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem
- An O(n2log n) parallel max-flow algorithm
- Finding Dominators in Directed Graphs
- scientific article; zbMATH DE number 3688740 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3475221 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- A decomposition algorithm for multi-terminal network flows
- The parallel complexity of finding a blocking flow in a 3-layer network
- Worst case behavior of the Dinic algorithm
- A new Karzanov-type O(n^ 3) max-flow algorithm
- A parallel algorithm for finding a blocking flow in an acyclic network
- A heuristic for blocking flow algorithms
- Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs
- Solving combinatorial problems with combined min-max-min-sum objective and applications
- On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions
- Minimal blocking flow in networks
- A competitive two-agent scheduling problem on parallel machines with release dates and preemption
- On implementing push-relabel method for the maximum flow problem
- Asymmetrical multiconnection three‐stage clos networks
- M-alternating paths and the construction of defect \(n\)-extendable bipartite graphs with different connectivities
- On blockers and transversals of maximum independent sets in co-comparability graphs
- Structural and algorithmic properties for parametric minimum cuts
- The maximum flow problem: A max-preflow approach
This page was built for publication: A simple version of Karzanov's blocking flow algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795064)
