Worst case behavior of the Dinic algorithm

DOI10.1016/0893-9659(91)90145-LzbMATH Open0738.90025MaRDI QIDQ1180321FDOQ1180321

Authors: Gary R. Waissi 

Publication date: 27 June 1992

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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

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)