A Systolic Design for Connectivity Problems

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.