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 log2 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^2 to n^3 steps. CACM September, 1972 Levitt, K. N. Kautz, W. H. graph theory, cellular logic-in-memory arrays, parallel processing, special purpose computers, algorithms for distance and spanning tree problems 5.32 6.22 6.5 CA720901 JB January 30, 1978 9:16 AM 2289 5 2289 2289 5 2289 2289 5 2289 3075 5 2289 3156 5 2289 2289 6 2289 2289 6 2289 2557 6 2289 2664 6 2289 2714 6 2289 2973 6 2289 3075 6 2289