A Systolic Design for Connectivity Problems
- 1 January 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (1) , 99-104
- https://doi.org/10.1109/tc.1984.5009318
Abstract
In this paper we present a design, suited to VLSI implementation, for a one-dimensional array to solve graph connectivity problems. The computational model is relatively primitive in that only the two end cells of the array can interact with the external environment and only adjacent cells in the array are allowed to communicate. However, we show that an array of n + 1 cells can be used for a graph with n vertices to find the connected components, a spanning tree, or, when used in conjunction with a systolic priority queue, a minimum spanning tree. The area, time, and I/O requirements compare favorably with other models proposed for this problem in the case of sparse graphs.Keywords
This publication has 7 references indexed in Scilit:
- A Dictionary Machine (for VLSI)IEEE Transactions on Computers, 1982
- Lower bounds for VLSIPublished by Association for Computing Machinery (ACM) ,1981
- The Parallel Recognition of Classes of GraphsIEEE Transactions on Computers, 1980
- The Design of Special-Purpose VLSI ChipsComputer, 1980
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972