Worst case behavior of the Dinic algorithm

DOI10.1016/0893-9659(91)90145-LzbMath0738.90025MaRDI QIDQ1180321

Gary R. Waissi

Publication date: 27 June 1992

Published in: Applied Mathematics Letters (Search for Journal in Brave)

zbMATH Keywords

acyclic networksDinic algorithmmax-flow phase algorithmsworst cae behavior

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Mathematical estimation for maximum flow of goods within a cross-dock to reduce inventory

Cites Work

• 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(n2log n) parallel max-flow algorithm