On the Parallel Computation of the Algebraic Path Problem.
Journal
IEEE Trans. Parallel Distrib. Syst.
Journal Volume
3
Journal Issue
2
Pages
251-256
Date Issued
1992
Author(s)
Abstract
The algebraic path problem is a general description of a class of problems, including some important graph problems such as transitive closure, all pairs shortest paths, minimum spanning tree, etc. In this paper, the algebraic path problem is solved on the processor array with a reconfigurable bus system. The proposed algorithms are based on repeated matrix multiplications. The multiplication of two n x n matrices takes O(log n) time in the worst case. But, for some special cases, 0(1) time is possible. It is shown that three instances of the algebraic path problem: transitive closure, all pairs shortest paths, and minimum spanning tree, can be solved in O(log n) time, which is as fast as on the CRCW PRAM. © 1992 IEEE
Type
journal article