A new Karzanov-type \(O(n^ 3)\) max-flow algorithm
From MaRDI portal
Publication:1197076
DOI10.1016/0895-7177(92)90007-8zbMath0759.90029MaRDI QIDQ1197076
Publication date: 16 January 1993
Published in: Mathematical and Computer Modelling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0895-7177(92)90007-8
maximal flow; directed single commodity networks; layered networks; maximum value flows; phase algorithms
90B10: Deterministic network models in operations research
90-08: Computational methods for problems pertaining to operations research and mathematical programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple version of Karzanov's blocking flow algorithm
- 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
- A data structure for dynamic trees
- A Fast and Simple Algorithm for the Maximum Flow Problem
- A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
- A comparison of phase and nonphase network flow algorithms
- An O(n2log n) parallel max-flow algorithm
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems