Faster parametric shortest path and minimum‐balance algorithms
- 1 March 1991
- Vol. 21 (2) , 205-221
- https://doi.org/10.1002/net.3230210206
Abstract
We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum‐balance algorithm to obtain a faster minimum‐balance algorithm.For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum‐balance algorithm both run in O(nm + n2 log n) time, improved from O(nm log n) for the parametric shortest path algorithm of Karp and Orlin and O(n2m) for the minimum‐balance algorithm of Schneider and Schneider.An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O(n log n + m).Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Finding minimum-cost circulations by canceling negative cyclesJournal of the ACM, 1989
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Computing optimal scalings by parametric network algorithmsMathematical Programming, 1985
- Amortized Computational ComplexitySIAM Journal on Algebraic Discrete Methods, 1985
- A minimum concave-cost dynamic network flow problem with an application to lot-sizingNetworks, 1985
- Parametric shortest path algorithms with an application to cyclic staffingDiscrete Applied Mathematics, 1981
- Applications of Path Compression on Balanced TreesJournal of the ACM, 1979
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978