2289	 Cellular Arrays for the Solution of Graph Problems	 A cellular array is a two-dimensional checkerboard type interconnection of identical modules or cells where each cell contains a few bits of memory and a small amount of combinational logic and communicates mainly with its immediate neighbors in the array. The chief computational advantage offered by cellular arrays is the improvement in speed achieved by virtue of the possibilities for parallel processing. In this paper it is shown that cellular arrays are inherently well suited for the solution of many graph problems. For example the adjacency matrix of a graph is easily mapped onto an array each matrix element is stored in one cell of the array and typical row and column operations are readily implemented by simple cell logic. A major challenge in the effective use of cellular arrays for the solution of graph problems is the determination of algorithms that exploit the possibilities for parallelism especially for problems whose solutions appear to be inherently serial. In particular several parallelized algorithms are presented for the solution of certain spanning tree distance and path problems with direct applications to wire routing PERT chart analysis and the analysis of many types of networks. These algorithms exhibit a computation time that in many cases grows at a rate not exceeding log n where n is the number of nodes in the graph. Straightforward cellular implementations of the well-known serial algorithms for these problems require about n steps and noncellular implementations require from n to n steps. graph theory cellular logic-in-memory arrays parallel processing special purpose computers algorithms for distance and spanning tree problems
