Computing Prufer codes efficiently in parallel

A Prufer code of a labeled free tree with n nodes is a sequence of length n - 2 constructed by the following sequential process: for i ranging from 1 to n - 2 insert the label of the neighbor of the smallest remaining leaf in to the ith position of the sequence, and then delete the leaf. Prufer codes provide an alternative to the usual representation of trees. We present an optimal O(log n) time, n/log n processor EREW-PRAM algorithm for determini ng the Prufer code of an n-node labeled chain and an O(log n) time, n proce ssor EREW-PRAM algorithm for constructing the Prufer code of an n-node labe led free tree. This resolves an open question posed by Wang et al. (IEEE Tr ans. Parallel Distributed Systems 8 (12) (1997) 1236-1240), (C) 2000 Elsevi er Science B.V. All rights reserved.