Fast reconfigurable network for graph connectivity and transitive closure

This paper presents a VLSI array for labeling the connected components of a graph on N nodes in O(r) steps using a reconfigurable bus of width m bits, such that (_r^m)≥N and 1≤r≤m. The network architecture consists of an array of simple logic nodes which are connected by a reconfigurable bus.To solve a problem on N nodes, the array uses N processors and N(N-1)/2 switches. The proposed connectivity and transitive closure algorithms are based on a processor indexing scheme which employs constant-weight codes. It is shown that when r is a constant, then the algorithm takes O(1) time using a bus of width O(N^1/r), and when r = [log N/loglog N], the algorithm takes O(log N/loglog N) time using a bus or width O(log N) bits.