SCALING ALGORITHMS FOR THE SHORTEST PATHS PROBLEM

Authors
GOLDBERG AV
Citation
Av. Goldberg, SCALING ALGORITHMS FOR THE SHORTEST PATHS PROBLEM, SIAM journal on computing, 24(3), 1995, pp. 494-504
Citations number
23
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
24
Issue
3
Year of publication
1995
Pages
494 - 504
Database
ISI
SICI code
0097-5397(1995)24:3<494:SAFTSP>2.0.ZU;2-R
Abstract
We describe a new method for designing scaling algorithms for the sing le-source shortest paths problem and use this method to obtain an O(ro ot nm log N) algorithm for the problem. (Here n and m are the number o f nodes and arcs in the input network and N is essentially the absolut e value of the most negative arc length; arc lengths are assumed to be integral.) This improves previous bounds for the problem. The method extends to related problems.