A simple version of Karzanov's blocking flow algorithm
From MaRDI portal
Publication:795064
DOI10.1016/0167-6377(84)90076-2zbMath0542.05057OpenAlexW1991295190MaRDI QIDQ795064
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
Deterministic network models in operations research (90B10) Graph theory (05C99) Algorithms in computer science (68W99)
Related Items (14)
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
This page was built for publication: A simple version of Karzanov's blocking flow algorithm
