Title :
Digital circuit implementation of a continuous-time inference network for the transitive closure problem
Author :
Su, C.J. ; Lam, K.P.
Author_Institution :
Dept. of Electr. Eng., British Columbia Univ., Vancouver, BC, Canada
Abstract :
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 log2(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
Keywords :
computational complexity; constraint theory; digital circuits; directed graphs; inference mechanisms; optimisation; travelling salesman problems; N-node directed graph problem; binary AND operation; binary relation inference networks; constraint satisfaction; continuous-time inference network; digital circuit implementation; interconnected units; optimization problems; scalar multiple; shortest path applications; time complexity; time/location-referencing; transitive closure problem; Artificial intelligence; Constraint optimization; Database systems; Digital circuits; Graph theory; Integrated circuit interconnections; Joining processes; Labeling; Numerical simulation; Parallel processing;
Conference_Titel :
Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on
Conference_Location :
Chicago, IL
Print_ISBN :
0-7803-1281-3
DOI :
10.1109/ISCAS.1993.394123