Worst case behavior of the Dinic algorithm

DOI10.1016/0893-9659(91)90145-LMaRDI QIDQ1180321zbMATH OpenFDO

Authors 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)

Recommendations

• On the efficiency of maximum-flow algorithms on networks with small integer capacities
• Quick max-flow algorithm
• A comparison of phase and nonphase network flow algorithms
• A new Karzanov-type O(n^ 3) max-flow algorithm

Cites work

• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A simple version of Karzanov's blocking flow algorithm
• An O(n2log n) parallel max-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

Cited in

(2)

• Exact Worst Case TCAM Rule Expansion
• Mathematical estimation for maximum flow of goods within a cross-dock to reduce inventory

This page was built for publication: Worst case behavior of the Dinic algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1180321)