Parallel asynchronous algorithms for the K shortest paths problem

Parallel asynchronous algorithms for the K shortest paths problem

0.00 Avg rating0 Votes
Article ID: iaor2001456
Country: United States
Volume: 104
Issue: 1
Start Page Number: 91
End Page Number: 108
Publication Date: Jan 2000
Journal: Journal of Optimization Theory and Applications
Authors: ,
Abstract:

We deal with the problem of computing in parallel the first K shortest paths from a single origin node to all other nodes of a directed graph. Our approach is based on a very easy way to introduce parallelism in the typical sequential label-correcting method. We describe formally an asynchronous method defined on a shared-memory parallel computational model, and we prove its theoretical correctness under very weak assumptions. According to different strategies used to implement the generic method, we propose several parallel label-correcting algorithms, and we analyze the numerical performance of the resulting codes on a nonuniform memory access multiprocessor via computational results collected on random generated networks. The advantage of parallelism is significant for very large-scale problems of practical interest.

Reviews

Required fields are marked *. Your email address will not be published.