A FULLY PIPELINED MINIMUM-SPANNING-TREE CONSTRUCTOR

[[abstract]]The author first develops a function, which he calls function F, and then proposes a novel systolic algorithm for the minimum-spanning-tree problem. The proposed algorithm is based on Tarjan's on-line approach. Consider a weighted undirected connected graph of n vertices and m edges. The proposed algorithm uses a systolic array of (n-1) pipelined cells. Adopting the on-line approach, the edges of the graph are fed into the array one by one in arbitrary order in each systolic cycle. When the last edge is fed into and processed by the first cell, the array turns into output phase, during which the edges of a minimum spanning tree of the graph are delivered out of the array one by one in each systolic cycle. Since the constructing time is overlapped with the input and output times, the time complexity of the algorithm is O(m+n) with O(m) for input and O(n) for output. In the algorithm, function F is used to realize find and join operations usually encountered in the connectivity problem in the literature. Because of the mathematic treatment, function F makes the realization of such operations simpler than other similar designs[[fileno]]2030249010006[[department]]資訊工程學