Parallel asynchronous label-correcting methods for shortest paths

被引：36

作者：

Bertsekas, DP ^{[1
]}

Guerriero, F ^{[1
]}

Musmanno, R ^{[1
]}

机构：

[1] UNIV CALABRIA,DIPARTIMENTO ELETTRON INFORMAT & SISTEMIST,I-87036 RENDE,ITALY

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 1996年 / 88卷 / 02期

关键词：

shortest path problems; parallel asynchronous algorithms; shared memory multiprocessors; label-correcting methods;

D O I：

10.1007/BF02192173

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：297 / 320

页数：24

共 21 条

[1]

[Anonymous], 2010, Dynamic programming

[2]

Bertsekas D. P., 1995, Computational Optimization and Applications, V4, P99, DOI 10.1007/BF01302891

[3]

Bertsekas D. P., 1992, DATA NETWORKS

[4]

Bertsekas Dimitri P., 1989, PARALLEL DISTRIBUTED

[5] A SIMPLE AND FAST LABEL CORRECTING ALGORITHM FOR SHORTEST PATHS [J].

BERTSEKAS, DP .

NETWORKS, 1993, 23 (08) :703-709

[6] DISTRIBUTED DYNAMIC-PROGRAMMING [J].

BERTSEKAS, DP .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1982, 27 (03) :610-616

[7]

Bertsekas DP., 1991, Linear network optimization: algorithms and codes

[8]

BERTSEKAS DP, 1986, MATH PROGRAMMING STU, V26, P38

[9]

BERTSEKAS DP, 1992, LIDSP2250 MIT

[10]

BERTSEKAS DP, 1991, PARALLEL COMPUT, V1, P707

← 1 2 3 →