An \(O(EV\log^2V)\) algorithm for the maximal flow problem

DOI10.1016/0022-0000(80)90035-5zbMath0449.90094OpenAlexW2091084079MaRDI QIDQ1147636

Zvi Galil, Amnon Naamad

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(80)90035-5

zbMATH Keywords

asymptotic behaviorimplementationnumerical analysiscomparison of algorithmsflows in networkspath compressionmaximal flow problemunion find algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (15)

Recent developments in maximum flow algorithms ⋮ On the efficiency of maximum-flow algorithms on networks with small integer capacities ⋮ The complexity of minimum partial truth assignments and implication in negation-free formulae ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Efficient regularized isotonic regression with application to gene-gene interaction search ⋮ Least squares isotonic regression in two dimensions ⋮ Worst case behavior of the Dinic algorithm ⋮ A new Karzanov-type \(O(n^ 3)\) max-flow algorithm ⋮ Polynomial auction algorithms for shortest paths ⋮ A parallel algorithm for finding a blocking flow in an acyclic network ⋮ Computational investigations of maximum flow algorithms ⋮ A data structure for dynamic trees ⋮ A simple version of Karzanov's blocking flow algorithm ⋮ The set union problem with dynamic weighted backtracking ⋮ The maximum flow problem: A max-preflow approach

Cites Work

• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Maximal Flow Through a Network
• Maximum Flow in Planar Networks
• Efficiency of a Good But Not Linear Set Union Algorithm
• 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(EV\log^2V)\) algorithm for the maximal flow problem