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)

Review text

The subject of this paper is two variants of the classical path- augmentation algorithm for maximum capacitated flow problem. The main point of the paper is that both algorithms have polynomial bounds even when the capacities have real values. The first bound is \(O(m^ 2\log m)\) flow augmentations and \(O(m^ 3\log m)\) operations. In the second case, a network simplex implementation, the number of simplex pivots is bounded by \(O(m^ 2 n^ 2\log m)\) and the number of operations by \(O(m^ 2 n^ 3\log m)\), where \(m\) is the number of arcs and \(n\) the number of nodes.

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)