文章基本信息

标题：A Comparison of two Parallel Iterative Algorithms for Solving Path Problems
本地全文：下载
作者：Manger, Robert
期刊名称：Journal of Computing and Information Technology
印刷版ISSN：1330-1136
电子版ISSN：1846-3908
出版年度：1996
卷号：4
期号：2
页码：75-85
语种：English
出版社：SRCE - Sveučilišni računski centar
摘要：Path problems are a family of optimization and enumeration problems posed on a directed graph. General algorithms for solving path problems can be designed as counterparts of the traditional iterative methods for solving linear systems. In this paper two parallel iterative Gauss-Seidel-like algorithms for solving path problems arc compared. Theoretical results are listed, which estimate the computational complexity of both algorithms. Experiments are presented, where the algorithms have been tested on randomly generated graphs and with different numbers of available processors. Some situations are identified, where one of the algorithms becomes superior to the other.
关键词：directed graphs; path problems; parallel algorithms; iterative methods; complexity; experiments