A FAST PARALLEL ALGORITHM FOR SOLVING PATH PROBLEMS

IN DAG-S by Robert Manger, Zagreb, Croatia

Abstract. 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. Mathematics subject classification: 68Q10, 68Q25, 68R10, 65F. Keywords: parallel algorithms, path problems, directed acyclic graphs.