Naslov
A Comparison of two Parallel Iterative Algorithms for Solving Path Problems

Autori
Manger, Robert

Izvornik
CIT : Journal of computing and information technology (1330-1136) 4 (1996), 2; 75-85

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
directed graphs; path problems; parallel algorithms; iterative methods; complexity; experiments

Sažetak
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 are 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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA