Parallel calculation of shortest paths in sparse graphs on a systolic array
- 6 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 422-425
- https://doi.org/10.1109/iccd.1988.25736
Abstract
The applicability of the systolic/wavefront array concept for a particular class of algorithms is evaluated. A representative of this class if Ford's algorithm (see E.L. Lawler, 1976) for the solution of the single-source-shortest-path problem under consideration of sparsity properties of the graph. Data transportation turns out to be the crucial point of the systolic realization. In the case of Ford's algorithm two different kinds of data transport problems arise which are solved by broadcasting within a connected region and by use of a two-dimensional systolic sorting procedure. Further, a comparison between the systolic version of Ford's algorithm and systolic realizations of Floyd's method (see E.L. Lawler, 1976), which is the corresponding direct algorithm, are given.Keywords
This publication has 6 references indexed in Scilit:
- A shortperiodic two-dimensional systolic sorting algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Regular iterative algorithms and their implementation on processor arraysProceedings of the IEEE, 1988
- A systolic array for cyclic-by-rows Jacobi algorithmsJournal of Parallel and Distributed Computing, 1987
- A systolic array algorithm for the algebraic path problem (shortest paths; Matrix inversion)Computing, 1985
- The VLSI Complexity of SortingIEEE Transactions on Computers, 1983
- Why systolic architectures?Computer, 1982