GREEDY PARTITIONED ALGORITHMS FOR THE SHORTEST-PATH PROBLEM

被引：0
|
作者：
ADAMSON, P [1 ]
TICK, E [1 ]
机构：
[1] UNIV OREGON,DEPT COMP SCI,EUGENE,OR 97403
来源：
INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING | 1992年 / 20卷 / 04期
关键词：
PARALLEL GRAPH ALGORITHMS; CONCURRENT LOGIC PROGRAMMING; PARTITIONING;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A partitioned, priority-queue algorithm for solving the single-source best-path problem is defined and evaluated. Finding single-source paths for sparse graphs is notable because of its definite lack of parallelism-no known algorithms are scalable. Qualitatively, we discuss the close relationships between our algorithm and previous work by Quinn, Chikayama, and others. Performance measurements of variations of the algorithm, implemented both in concurrent and imperative programming languages on a shared-memory multiprocessor, are presented. This quantitative analysis of the algorithms provides insights into the tradeoffs between complexity and overhead in graph-searching executed in high-level parallel languages with automatic task scheduling.
引用
收藏
页码：271 / 298
页数：28
相关论文
共 50 条
  • [21] NOTE ON THE SHORTEST-PATH PROBLEM - REPLY
    ROMANI, F
    INFORMATION PROCESSING LETTERS, 1981, 13 (02) : 87 - 87
  • [22] APPLICATIONS OF SHORTEST-PATH ALGORITHMS TO MATRIX SCALINGS
    VONGOLITSCHEK, M
    SCHNEIDER, H
    NUMERISCHE MATHEMATIK, 1984, 44 (01) : 111 - 126
  • [23] SHORTEST-PATH AND CLOSURE ALGORITHMS FOR BANDED MATRICES
    ALLISON, L
    DIX, TI
    YEE, CN
    INFORMATION PROCESSING LETTERS, 1991, 40 (06) : 317 - 322
  • [24] ASYMPTOTIC OPTIMALITY OF SHORTEST-PATH ROUTING ALGORITHMS
    GAFNI, EM
    BERTSEKAS, DP
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1987, 33 (01) : 83 - 90
  • [25] Shortest-Path Algorithms and Dynamic Cost Changes
    Baselau, Sven
    Hahne, Felix
    Ambrosi, Klaus
    OPERATIONS RESEARCH PROCEEDINGS 2007, 2008, : 111 - 116
  • [26] DISTRIBUTED COMPUTATION ON GRAPHS - SHORTEST-PATH ALGORITHMS
    CHANDY, KM
    MISRA, J
    COMMUNICATIONS OF THE ACM, 1982, 25 (11) : 833 - 837
  • [27] LEVEL GRAPHS AND APPROXIMATE SHORTEST-PATH ALGORITHMS
    SHAPIRO, J
    WAXMAN, J
    NIR, D
    NETWORKS, 1992, 22 (07) : 691 - 717
  • [28] Speeding up dynamic shortest-path algorithms
    Buriol, Luciana S.
    Resende, Mauricio G. C.
    Thorup, Mikkel
    INFORMS JOURNAL ON COMPUTING, 2008, 20 (02) : 191 - 204
  • [29] ON THE EQUIVALENCE BETWEEN SOME SHORTEST-PATH ALGORITHMS
    SHERALI, HD
    OPERATIONS RESEARCH LETTERS, 1991, 10 (02) : 61 - 65
  • [30] Faster shortest-path algorithms for planar graphs
    Henzinger, MR
    Klein, P
    Rao, S
    Subramanian, S
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 55 (01) : 3 - 23
12345