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: | Guerriero F., Musmanno R. |
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.