Optimal Graph Algorithms on Linear Arrays

Abstract

We consider a computational model based on a fixed-size linear array. Based on this model, we develop a number of techniques that lead to optimal algorithms for a number of combinatorial problems. Specifically, we develop optimal algorithms for determining the connected components, the minimum spanning forest, the bridges, and the articulation points of an undirected graph, and the pseudo-open ear decomposition, and the biconnected components of a connected undirected graph. We also develop optimal algorithms to solve the list ranking and the convex hull problems. The input to each of our graph algorithms is a set of edges, distributed evenly among the processors. Our graph algorithms run in Theta(m/p + n + p) time, where m is the number of edges, n is the number of vertices, and p is the number of processors, which is between 1 and m. The convex hull algorithm runs in Theta((n log n)/p + n ) time, which can be shown to be the best possible on a p-processor linear array for p between 1 and n. Further, we implement our Connected Components algorithm on the ParsyTec SuperCluster Transputers, which contains 32 IMS T800 transputers. The implementations are done with two different logical network configurations and data broadcasting topologies corresponding to a pipeline model and a tree model. We construct the physical interconnection network among the processors as a linear array. We evaluate the algorithm performance on each of these two models and make comparisons between the two. We have run experiments on many graphs of different sizes and processors, and the results show communication costs dominate whenever we have more than four processors for problems of sizes up to 100 vertices or 4000 edges. Furthermore, the algorithm based on the binary tree logical network runs better than the one based on the linear array logical network.