Naslov
Parallel iterative algorithms for solving path problems

Autori
Manger, Robert

Izvornik
Journal of Computing and Information Technology - CIT (1330-1136) 1 (1993), 2; 99-110

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

Ključne riječi
directed graphs; path problems; algebraic approach; parallel computing; iterative algorithms

Sažetak
Path problems are a family of optimization and enumeration problems involving the determination of paths in directed graphs. In this paper few parallel iterative algorithms for solving path problems are developed. More precisely, the considered algorithms are parallelized counterparts of the classical iterative methods, such as Jacobi or Gauss-Seidel. The underlying model of computation is a tightly coupled multiprocessor. It is shown that the algorithms obtain the required solution after a finite number of iterations. For each algorithm, the computational complexity of a single iteration is estimated, and an upper bound for the number of iterations is established. On the basis of these results the algorithms are compared.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA