On the maximum capacity augmentation algorithm for the maximum flow problem

DOI10.1016/0166-218X(93)90148-HMaRDI QIDQ1314319zbMATH OpenOpenAlexWikidataFDO

Authors Jianxiu Hao, Donald Goldfarb

Publication date 22 February 1994

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(93)90148-h

zbMATH Keywords

maximum capacitated flownetwork simplex implementationpath-augmentation algorithmpolynomial bounds

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the efficiency of maximum-flow algorithms on networks with small integer capacities
• Improved Time Bounds for the Maximum Flow Problem
• Strongly polynomial dual simplex methods for the maximum flow problem
• A Fast and Simple Algorithm for the Maximum Flow Problem
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time

Cites work

• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time
• A strongly polynomial minimum cost circulation algorithm
• Algorithms for maximum network flow
• scientific article; zbMATH DE number 4204092 (Why is no real title available?)
• scientific article; zbMATH DE number 193993 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• Theoretical Efficiency of the Algorithm “Capacity” for the Maximum Flow Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Cited in

(15)

• On the efficiency of maximum-flow algorithms on networks with small integer capacities
• An incremental algorithm for the maximum flow problem
• Maximum network flow with floating point arithmetic.
• Augmenting approach for some maximum set problems
• New algorithm for maximum flow algorithm in network with both node and edge capacity confined
• scientific article; zbMATH DE number 3906194 (Why is no real title available?)
• Layered Augmenting Path Algorithms
• Maximum flow in a network with an underestimated arc capacity
• scientific article; zbMATH DE number 2163908 (Why is no real title available?)
• A capacity scaling algorithm for the constrained maximum flow problem
• Generalized max flows and augmenting paths
• Fast augmentation algorithms for maximising the output flow in repairable flow networks after edge failures
• On a capacity scaling algorithm for the constrained maximum flow problem
• Weakly and strongly polynomial algorithms for computing the maximum decrease in uniform arc capacities
• An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems

This page was built for publication: On the maximum capacity augmentation algorithm for the maximum flow problem

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