A simple version of Karzanov's blocking flow algorithm

DOI10.1016/0167-6377(84)90076-2MaRDI QIDQ795064zbMATHOpenAlexFDO

Authors Robert E. 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)

Recommendations

• A new Karzanov-type \(O(n^ 3)\) max-flow algorithm
• scientific article; zbMATH DE number 177817
• scientific article; zbMATH DE number 1766747
• A new approach to the maximum-flow problem
• An $o(n^3 )$-Time Maximum-Flow Algorithm

Cites work

• 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?)
• An O(n2log n) parallel max-flow algorithm
• 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
• Finding Dominators in Directed Graphs

Cited in

(17)

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

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)