求解SSSP问题图运算的复制数据算法*
作者:

A STUDY ON THE REPLlCATED DATA ALGORITHM FOR SOLVING THE SINGLE SOURCE SHORTEST PATH PROBLEM
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [1]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    本文首先提出求解SSSP问题图运算的数据并行算法及复制数据算法,并把复制数据技术成功地用于求解SSSP问题图运算证明算法的有效性,然后计算并讨论复制数据算法对数据并行算法的加速,最后指出复制数据技术不仅能用于图象的快速分析,而且也能广泛地用于解各种图运算问题.

    Abstract:

    This paper first proposes a data parallel algorithm and a replicated data algo-rithm for the graph theoretic operation of computing the single source shortest paths and demonstrates the generality of the data replicated technique by applying it to the graph theoretic operation for solving SSSP problems,then computes and discusses the speedup of the replicated data algorithm over the data parallel algorithm,finally points out that the data replication technique is not only applicable to fast image analysis,hut also is general enouth to be applicable to a large class of the graph theoretic operation problems.

    参考文献
    1 Dijkstra E W. A note on two problems in connexion with graphs.Numerische Mithematik,1959, 1:269~271. 2 Paige R C, Kruskal C P.Parallel algorithms for shortest path problems.In:Proc.of the International Conference on Parallel Processing,1985.14~19. 3 Floyd R W.Algorithm 97:shortest path.Communications of the ACM,1962,5:345~348. 4 Cypher R, Sanz J L C.SIMD architectures and algorithms for image processing and computer vision.IEEE Trans.on Acoustics,Speech and Signal Processing,1989,37:2158~2173. 5 Chan T F,Saad Y.Multigrid algorithms on the hypercube multiprocessor.IEEE Trans.on Computers,1986,35:969~977. 6 Preparata F P.Advances in computing research.Computational Geometry,JAI PRESS INC., 1983.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

杨敬安.求解SSSP问题图运算的复制数据算法*.软件学报,1996,7(zk):394-399

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1995-10-09
文章二维码
您是第19807598位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号