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

DOI10.1002/1520-6750(200009)47:6%3C511::AID-NAV4%3E3.0.CO;2-SMaRDI QIDQ4519920zbMATH OpenOpenAlexFDO

Authors Antonio Sedeño-Noda, C. González-Martín

Publication date 27 January 2002

Full work available at URL https://doi.org/10.1002/1520-6750(200009)47:6%3C511::aid-nav4%3E3.0.co;2-s

zbMATH Keywords

maximum flow algorithmnetworks

Mathematics Subject Classification ID

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

Recommendations

• An o(n^3 )-Time Maximum-Flow Algorithm
• Flows in Undirected Unit Capacity Networks
• Improved Time Bounds for the Maximum Flow Problem
• Max flows in O(nm) time, or better
• scientific article; zbMATH DE number 177817

Cites work

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

Cited in

(10)

• A computational study of the capacity scaling algorithm for the maximum flow problem
• A generalization of the scaling max-flow algorithm
• Inverse feasibility problems of the inverse maximum flow problems
• Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks
• scientific article; zbMATH DE number 7051295 (Why is no real title available?)
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Breaking the \(O(n^{2.5})\) deterministic time barrier for undirected unit-capacity maximum flow
• A fast maximum flow algorithm
• An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem
• The binary network flow problem is logspace complete for P

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

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