首页> 外文期刊>Computing and informatics >EFFICIENT PARALLEL IMPLEMENTATION OF THE RAMALINGAM DECREMENTAL ALGORITHM FOR UPDATING THE SHORTEST PATHS SUBGRAPH
【24h】

EFFICIENT PARALLEL IMPLEMENTATION OF THE RAMALINGAM DECREMENTAL ALGORITHM FOR UPDATING THE SHORTEST PATHS SUBGRAPH

机译:更新最短路径子图的RAMALINGAM递归算法的有效并行实现

获取原文
获取原文并翻译 | 示例

摘要

We propose an efficient parallel implementation of the Ramalingam algorithm for dynamic updating the shortest paths subgraph of a directed weighted graph with a sink after deletion of an edge. To this end, a model of associative (content addressable) parallel systems with vertical processing (the STAR-machine) is used. On the STAR-machine, the Ramalingam decremental algorithm for dynamic updating the shortest paths subgraph is represented as the main procedure DeleteArc that uses a group of auxiliary procedures. We provide the DeleteArc procedure along with the auxiliary procedures, prove correctness of these procedures and evaluate the time complexity. We also consider an example of implementing the DeleteArc procedure on the STAR-machine.
机译:我们提出了Ramalingam算法的高效并行实现,用于在删除边后动态更新带有接收器的有向加权图的最短路径子图。为此,使用了具有垂直处理的关联(内容可寻址)并行系统模型(STAR机器)。在STAR机器上,用于动态更新最短路径子图的Ramalingam递减算法表示为使用一组辅助过程的主要过程DeleteArc。我们提供DeleteArc过程以及辅助过程,证明这些过程的正确性并评估时间复杂度。我们还考虑在STAR计算机上实现DeleteArc过程的示例。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号