Abstract
A bus system whose configuration can be dynamically changed is a reconfigurable bus system. In this paper, on processor arrays with reconfigurable bus systems, two O(1) time algorithms are proposed for computing the transitive closure of an undirected graph. One is designed on a three-dimensional nxnxn processor array with a reconfigurable bus system and the other is designed on a two-dimensional n2 x n2 processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Using the O(1) time transitive closure algorithms, we also solve many other graph problems in O(1) time. These problems include recognizing bipartite graphs and finding connected components, articulation points, biconnected components, bridges, and minimum spanning trees in undirected graphs. © 1990 IEEE