A simple version of Karzanov's blocking flow algorithm

DOI10.1016/0167-6377(84)90076-2zbMath0542.05057OpenAlexW1991295190MaRDI QIDQ795064

Robert Endre Tarjan

Publication date: 1984

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(84)90076-2

zbMATH Keywords

graph algorithmmaximum flow problem

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Graph theory (05C99) Algorithms in computer science (68W99)

Related Items

A decomposition algorithm for multi-terminal network flows, Asymmetrical multiconnection three‐stage clos networks, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, On implementing push-relabel method for the maximum flow problem, A competitive two-agent scheduling problem on parallel machines with release dates and preemption, Worst case behavior of the Dinic algorithm, A new Karzanov-type \(O(n^ 3)\) max-flow algorithm, M-alternating paths and the construction of defect \(n\)-extendable bipartite graphs with different connectivities, Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs, Structural and algorithmic properties for parametric minimum cuts, A parallel algorithm for finding a blocking flow in an acyclic network, A heuristic for blocking flow algorithms, Solving combinatorial problems with combined min-max-min-sum objective and applications, The maximum flow problem: A max-preflow approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O(EV\log^2V)\) algorithm for the maximal flow problem
• An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• An O(n2log n) parallel max-flow algorithm
• Finding Dominators in Directed Graphs