Constant time algorithms for Euler tour and tree operations on CRAP
Young Hak Kim, Jik Hyun Chang · 2002
A cross-bridge reconfigurable array of processors (CRAP) is a parallel processing system which has the ability to change dynamically its interconnection scheme during the execution of an algorithm. In this paper, given an unrooted tree T with n vertices, we propose an O(1) time algorithm for constructing an Euler tour of T on a 2-D (dimensional) n/spl Gt/MULT(n-1) CRAP. Then, given a root vertex r, we present O(1) time algorithms for tree operations which compute the parent and the preorder/postorder number of each vertex, the number of vertices in the subtree rooted at each vertex, and the level of each vertex.