Title :
Regular iterative algorithm for extracting all trees of a linear graph
Author :
Joshi, Shridhar P. ; Priemer, Roland
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Illinois Univ., Chicago, IL, USA
Abstract :
A regular iterative algorithm (RIA) to extract all trees of a linear graph is presented. The algorith is developed from a sequential algorithm that operates on the incidence matrix of a graph. This RIA can be used to design a processor array that can find trees of a graph at a rate that is independent of the number of graph edges. The RIA is the basis for a processor array that finds one tree of a graph in O(N) time, where N is the number of graph vertices
Keywords :
iterative methods; logic arrays; logic design; trees (mathematics); incidence matrix; linear graph; processor array; regular iterative algorithm; tree extraction; Circuits; Difference equations; Iterative algorithms; Optical wavelength conversion; Systolic arrays; Tree graphs;
Conference_Titel :
Circuits and Systems, 1992., Proceedings of the 35th Midwest Symposium on
Conference_Location :
Washington, DC
Print_ISBN :
0-7803-0510-8
DOI :
10.1109/MWSCAS.1992.271075
