Naslov
A fast parallel algorithm for solving path problems in DAG-s

Autori
Manger, Robert

Izvornik
Glasnik Matematički (0017-095X) 29 (1994), 1; 175-189

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

Ključne riječi
parallel algorithms; path problems; directed acyclic graphs
(arallel algorithms; path problems; directed acyclic graphs)

Sažetak
Path problems are a family of optimization and enumeration problems involving the determination of paths in directed graphs. This paper is concerned with the parallel solution of path problems in directed acyclic graphs (DAG-s). The assumed model of computation is a shared memory multiprocessor. A suitable algebraic formulation of path problems is used. A fast parallel algorithm is developed and proved to be correct. Its computational complexity is analyzed, in dependence on the input size and on the number of available processors. The considered algorithm really takes into account the assumed acyclicity, and therefore it is faster and more efficient than any method working in arbitrary graphs.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA