A simple version of Karzanov's blocking flow algorithm

DOI10.1016/0167-6377(84)90076-2zbMATH Open0542.05057OpenAlexW1991295190MaRDI QIDQ795064FDOQ795064

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Finding Dominators in Directed Graphs
• 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(n2log n) parallel max-flow algorithm

Cited In (17)

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

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)