A simple implementation of Warshall's algorithm on a vlsi chip

The key step in the Warshall's well known algorithm for transitive closure of a graph [1] involves a recurrence equation of the following type: (Formula presented.) where fø(i,j) ist the (i,j)th element of the adjacency matrix of the given graph and fn(i,j) the final required result. Van Scoy [2] proposed a scheme to implement Warshall's algorithm in O(n) time using n2 processors arranged in the form of a square with ‘Wraparound’ connections. But the algorithm and its proof of correctness are quite complicated with several subcases (The analysis of the content of ‘position’ register alone extends to 29 cases). Moreover, it is difficult to conceive of a design to solve a generalised recurrence equation of the type (Formula presented.) which occurs quite frequently as a key step in many graph theoretic algorithms [3]. In this paper we shall describe a new scheme with full details of the implementation, which is quite simple and suitable for VLSI chip fabrication. We shall also outline how the algorithm can be implemented even without wraparound connections. In both the cases the time taken to solve the problem is O(n).