Parallel Algorithms for Network Routing Problems and Recurrences
John A. Wisniewski, Ahmed Sameh · SIAM Journal on Algebraic and Discrete Methods · 1982
In this paper, we consider the parallel solution of recurrences, and linear systems in the regular algebra of Carré. These problems are equivalent to solving the shortest path problem in graph theory, and they also arise in the analysis of Fortran programs. Our methods for solving linear systems in the regular algebra are analogues of well-known methods for solving systems of linear algebraic equations. A parallel version of Dijkstra’s method, which has no linear algebraic analogue, is presented. Considerations for choosing an algorithm when the problem is large and sparse are also discussed.