Accession Number : ADA322745
Title : Scaling Algorithms for the Shortest Paths Problem,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Goldberg, Andrew
PDF Url : ADA322745
Report Date : MAY 1992
Pagination or Media Count : 15
Abstract : We give an O((square root of n)m log N) algorithm for the single-source shortest paths problem with integral arc lengths. (Here n and m is the number of nodes and arcs in the input network and N is essentially the absolute value of the most negative arc length.) This improves previous bounds for the problem.
Descriptors : *ALGORITHMS, OPTIMIZATION, INPUT OUTPUT PROCESSING, SCALING FACTOR, SUBROUTINES.
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE