Skip to main content
eScholarship
Open Access Publications from the University of California

Faster parametric shortest path and minimum‐balance algorithms

  • Author(s): Young, NE
  • Tarjant, RE
  • Orlin, JB
  • et al.

Published Web Location

https://arxiv.org/abs/cs/0205041
No data is associated with this publication.
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). Copyright © 1991 Wiley Periodicals, Inc., A Wiley Company

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item