Parallel asynchronous label-correcting methods for shortest paths |
| |
Authors: | D. P. Bertsekas F. Guerriero R. Musmanno |
| |
Affiliation: | (1) Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts;(2) Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabria, Rende, Italy |
| |
Abstract: | We develop parallel asynchronous implementations of some known and some new label-correcting methods for finding a shortest path from a single origin to all the other nodes of a directed graph. We compare these implementations on a shared-memory multiprocessor, the Alliant FX/80, using several types of randomly generated problems. Excellent (sometimes superlinear) speedup is achieved with some of the methods, and it is found that the asynchronous versions of these methods are substantially faster than their synchronous counterparts.The authors acknowledge the director and the staff of CERFACS, Toulouse, France for the use of the Alliant FX/80.This research was supported by the National Science Foundation under Grants 9108058-CCR, 9221293-INT, and 9300494-DMI. |
| |
Keywords: | Shortest path problems parallel asynchronous algorithms shared memory multiprocessors label-correcting methods |
本文献已被 SpringerLink 等数据库收录! |
|