Back to Search
Start Over
Tight bounds on the number of minimum-mean cycle cancellations and related results.
- Source :
- Algorithmica; Mar1994, Vol. 11 Issue 3, p226-242, 17p
- Publication Year :
- 1994
-
Abstract
- We prove a tight Θ(min( nm log(nC), nm)) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations to O(nm). We also give an improved version of the maximum-mean cut canceling algorithm of [7], which is a dual of the minimum-mean cycle-canceling algorithm. Our version of the dual algorithm runs in O(nm) iterations. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 11
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 71309343
- Full Text :
- https://doi.org/10.1007/BF01240734