An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem

DOI10.1007/BF00264254zbMath0456.68044MaRDI QIDQ1151034

Zvi Galil

Publication date: 1980

Published in: Acta Informatica (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items (11)

Local optima topology for the \(k\)-coloring problem ⋮ On the efficiency of maximum-flow algorithms on networks with small integer capacities ⋮ A new polynomial-time algorithm for the maximum weighted (?(G) ? 1)-coloring problem in comparability graphs ⋮ ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Worst case behavior of the Dinic algorithm ⋮ A new Karzanov-type \(O(n^ 3)\) max-flow algorithm ⋮ A parallel algorithm for finding a blocking flow in an acyclic network ⋮ Computational investigations of maximum flow algorithms ⋮ A simple version of Karzanov's blocking flow algorithm ⋮ The maximum flow problem: A max-preflow approach

Cites Work

• On the theoretical efficiency of various network flow algorithms
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem