MESH-CONNECTED PROCESSOR ARRAYS FOR THE TRANSITIVE CLOSURE PROBLEM FA6 = 11 :30
Sailesh K. Rao, Todd Citron, T. Kailath · 1985
The main purpose in this paper is to lay a theoretical foundation for the design of mesh-connected processor arra s for the transitive closure problem. Using a simple pat i algebraic formulation of the problem and observin its similarit to certain well-known smoothing roblems t at occur in Jgital signal processin , we show ow to draw upon existing techniques from t % e signal processing literature to derive regular iterative algorithms for determining the transitive closure of the graph. The regular iterative algorithms that are derived using these considerations, are then analyzed and s nthesized on mesh-connected processor arrays. Among t K e vast number of mesh-connected processor arrays that can be desi ned using this unified approach, the s stolic arrays reporte in the literature for this problem are s own to be special cases.