Premium
Faster parametric shortest path and minimum‐balance algorithms
Author(s) -
Young Neal E.,
Tarjant Robert E.,
Orlin James B.
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210206
Subject(s) - shortest path problem , shortest path faster algorithm , yen's algorithm , fibonacci number , k shortest path routing , suurballe's algorithm , widest path problem , mathematics , algorithm , parametric statistics , combinatorics , path (computing) , dijkstra's algorithm , graph , computer science , statistics , programming language
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 + n 2 log n ) time, improved from O ( nm log n ) for the parametric shortest path algorithm of Karp and Orlin and O ( n 2 m ) 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 ).