Digital circuit implementation of a continuous-time inference network for the transitive closure problem
C.J. Su, K.P. Lam · 1993 IEEE International Symposium on Circuits and Systems · 2002
A class of binary relation inference networks has been proposed for solving constraint satisfaction and optimization problems, especially those related with time/location-referencing and shortest path applications. An important extension of this type of network is described. It provides an efficient solution to the transitive closure problem. For a given N-node directed graph problem, the inference network consists of N(N-1) interconnected units, where (N-2) sites are attached to each of these units. Simple binary AND operation is required at each site. Each unit performs an (N-1)-input OR operation. The computation has a time complexity bounded by a scalar multiple of log/sub 2/(N-1), and can be executed in the continuous-time domain. Theoretical analysis on network convergence is discussed. Numerical simulation of a digital circuit implementation indicates a solution time in the time range of nanoseconds.>