On the maximum capacity augmentation algorithm for the maximum flow problem
type: Item
instance of: scholarly article
title: On the maximum capacity augmentation algorithm for the maximum flow problem
zbMATH Open document ID: 0810.90033
DOI: 10.1016/0166-218X(93)90148-H
author: Jianxiu Hao
author: Donald Goldfarb
published in: Discrete Applied Mathematics
publication date: 1994-02-22T00:00:00Z
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.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 501141
zbMATH Keywords: path-augmentation algorithm
zbMATH Keywords: maximum capacitated flow
zbMATH Keywords: polynomial bounds
zbMATH Keywords: network simplex implementation
MaRDI profile type: Publication
cites work: Q4040780
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Q5514188
cites work: Use of dynamic trees in a network simplex algorithm for the maximum flow problem
cites work: Q3352816
cites work: A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
cites work: Q4130999
cites work: Theoretical Efficiency of the Algorithm “Capacity” for the Maximum Flow Problem
cites work: A strongly polynomial minimum cost circulation algorithm
cites work: Algorithms for maximum network flow
full work available at URL: 0166-218x(93)90148-h
OpenAlex ID: W2091599791
Wikidata QID: Q127846169
description: scientific article; zbMATH DE number 501141