A RANDOMIZED PARALLEL ALGORITHM FOR SINGLE-SOURCE SHORTEST PATHS

Authors
KLEIN PN SUBRAMANIAN S
Citation
Pn. Klein et S. Subramanian, A RANDOMIZED PARALLEL ALGORITHM FOR SINGLE-SOURCE SHORTEST PATHS, Journal of algorithms, 25(2), 1997, pp. 205-220
Citations number
18
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
25
Issue
2
Year of publication
1997
Pages
205 - 220
Database
ISI
SICI code
0196-6774(1997)25:2<205:ARPAFS>2.0.ZU;2-W
Abstract
We give a randomized parallel algorithm for computing single-source sh ortest paths in weighted digraphs. We show that the exact shortest-pat h problem can be efficiently reduced to solving a series of approximat e shortest-path subproblems. Our algorithm for the approximate shortes t-path problem is based on the technique used by Ullman and Yannakakis in a parallel algorithm for breadth-first search. (C) 1997 Academic P ress.