AO(nm log(U/n)) time maximum flow algorithm

DOI<511::AID-NAV4>3.0.CO;2-S 10.1002/1520-6750(200009)47:6<511::AID-NAV4>3.0.CO;2-SzbMath0977.90076OpenAlexW1543904360MaRDI QIDQ4519920

Antonio Sedeño-Noda, Carlos González-Martín

Publication date: 27 January 2002

Full work available at URL: https://doi.org/10.1002/1520-6750(200009)47:6<511::aid-nav4>3.0.co;2-s

zbMATH Keywords

networksmaximum flow algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (3)

A generalization of the scaling max-flow algorithm ⋮ A computational study of the capacity scaling algorithm for the maximum flow problem ⋮ Inverse feasibility problems of the inverse maximum flow problems

Cites Work

• Scaling algorithms for network problems
• On the efficiency of maximum-flow algorithms on networks with small integer capacities
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• A data structure for dynamic trees
• A Fast and Simple Algorithm for the Maximum Flow Problem
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Maximal Flow Through a Network
• Improved Time Bounds for the Maximum Flow Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems
• An $o(n^3 )$-Time Maximum-Flow Algorithm

This page was built for publication: AO(nm log(U/n)) time maximum flow algorithm