COMPUTING TREE FUNCTIONS ON MESH-CONNECTED COMPUTERS.

Algorithms for computing several functions of an undirected tree that has n vertices using a q-dimensional mesh-connected computer having 2n-2 processors are presented. The functions computed are: finding an Euler circuit of the tree, constructing a directed tree from the undirected tree, preorder and postorder numbering of the vertices in the tree, computing the number of descendants of each vertex in the directed tree, and determining the path between two vertices in the tree. The tree is represented by a list of edges. Each undirected edge is represented by two directed edges in this list. In order to compute these functions on a mesh-connected computer, it is required that information stored in processors that are far apart be brought together. This is accomplished by using sorting as the key data movement operation in the algorithm, and all these functions are computed in O(q**2 n**1**/**Q log n) time.