Document Zbl 0842.90115

Bertsekas, D. P.; Guerriero, F.; Musmanno, R.

Parallel asynchronous label-correcting methods for shortest paths. (English) Zbl 0842.90115

J. Optimization Theory Appl. 88, No. 2, 297-320 (1996).

Summary: 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.

Cited in 1 Review

Cited in 9 Documents

MSC:

90C35	Programming involving graphs or networks
65Y05	Parallel numerical computation

Keywords:

shortest path problems; parallel asynchronous implementations; label-correcting methods; shared-memory multiprocessor

Software:

NETGEN

Cite Review PDF

Full Text: DOI

References:

[1]	Gallo, G., andPallottino, S.,Shortest Path Algorithms, Annals of Operations Research, Vol. 7, pp. 3–79, 1988.
[2]	Bertsekas, D. P.,An Auction Algorithm for the Shortest Path Problem, Mathematical Programming Study, Vol. 26, pp. 38–64, 1986.
[3]	Bertsekas, D. P., Pallottino, S., andScutella’, M. G.,Polynomial Auction Algorithms for Shortest Paths, Computational Optimization and Applications, Vol. 4, pp. 99–125, 1995. · Zbl 0835.90111 · doi:10.1007/BF01302891
[4]	Helgason, R. V., andStewart, D.,One-to-One Shortest Path Problem: An Empirical Analysis with the Two-Tree Dijkstra Algorithm, Computational Optimization and Applications, Vol. 2, pp. 47–75, 1993. · Zbl 0776.90083 · doi:10.1007/BF01299142
[5]	Polymenakos, L., andBertsekas, D. P.,Parallel Shortest Path Auction Algorithms, Parallel Computing, Vol. 20, pp. 1221–1247, 1994. · Zbl 0823.68086 · doi:10.1016/0167-8191(94)90035-3
[6]	Gallo, G., andPallottino, S.,Shortest Path Methods: A Unified Approach, Mathematical Programming Study, Vol. 26, pp. 38–64, 1986. · Zbl 0605.90123
[7]	Bellman, R.,Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1957. · Zbl 0077.13605
[8]	Bertsekas, D. P.,A Simple and Fast Label-Correcting Algorithm for Shortest Paths, Networks, Vol. 23, pp. 703–709, 1993. · Zbl 0801.90111 · doi:10.1002/net.3230230808
[9]	Glover, F., Glover, R., andKlingman, D.,The Threshold Shortest Path Algorithm, Networks, Vol. 14, pp. 256–282, 1986.
[10]	Pape, U.,Implementation and Efficiency of Moore Algorithms for the Shortest Path Problem, Mathematical Programming, Vol. 7, pp. 212–222, 1974. · Zbl 0288.90080 · doi:10.1007/BF01585517
[11]	Bertsekas, D. P.,Linear Network Optimization: Algorithms and Codes, MIT Press, Cambridge, Massachusetts, 1991. · Zbl 0754.90059
[12]	Bertsekas, D. P.,Distributed Dynamic Programming, IEEE Transactions on Automatic Control, Vol. 27, pp. 610–616, 1982. · Zbl 0493.49030 · doi:10.1109/TAC.1982.1102980
[13]	Bertsekas, D. P., andGallager, R. G.,Data Networks, 2nd Edition, Prentice-Hall, Englewood Cliffs, New Jersey, 1992.
[14]	Bertsekas, D. P., andTsitsiklis, J. N.,Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1989. · Zbl 0743.65107
[15]	Mohr, T., andPasche, C.,Parallel Shortest Path Algorithm, Computing, Vol. 40, pp. 281–292, 1990. · Zbl 0659.68089 · doi:10.1007/BF02276912
[16]	Träff, J. L.,Precis: Distributed Shortest Path Algorithms, Proceedings of the 5th International PARLE Conference, Munich, Germany, 1993; Springer Verlag, Berlin, Germany, pp. 720–723, 1993.
[17]	Dung, T., Hao, J., andKokur, G.,Label-Correcting Shortest Path Algorithms: Analysis and Implementation, Unpublished Report, GTE Laboratories, Waltham, Massachusetts, 1993.
[18]	Bertsekas, D. P., andCastanon, D. A.,Parallel Asynchronous Implementations of the Auction Algorithm, Parallel Computing, Vol. 1, pp. 707–732, 1991. · Zbl 0737.68036 · doi:10.1016/S0167-8191(05)80062-6
[19]	Klingman, D., Napier, A., andStutz, J.,NETGEN: A Program for Generating Large-Scale (Un) Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems, Management Science, Vol. 20, pp. 814–822, 1974. · Zbl 0303.90042 · doi:10.1287/mnsc.20.5.814
[20]	Bertsekas, D. P., Guerriero, F., andMusmanno, R.,Parallel Asynchronous Label-Correcting Methods for Shortest Paths, Report No. LIDS-P-2250, Massachusetts Institute of Technology, 1992. · Zbl 0842.90115
[21]	Brown, A. A., andBartholomew-Biggs, M. C.,Some Effective Methods for Unconstrained Optimization Based on the Solution of Systems of Ordinary Differential Equations, Report No. 78, Numerical Optimisation Centre, Hatfield Polytechnic, Hatfield, England, 1987. · Zbl 0651.90067

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.