A parallel algorithm for constructing a labeled tree

A tree T is labeled when the n vertices are distinguished from one another by names such as v₁, v₂…v_n . Two labeled trees are considered to be distinct if they have different vertex labels even though they might be isomorphic. According to Cayley´s tree formula, there are n^n-2 labeled trees on n vertices. Prufer used a simple way to prove this formula and demonstrated that there exists a mapping between a labeled tree and a number sequence. From his proof, we can find a naive sequential algorithm which transfers a labeled tree to a number sequence and vice versa. However, it is hard to parallelize. In this paper, we shall propose an O(log n) time parallel algorithm for constructing a labeled tree by using O(n) processors and O(n log n) space on the EREW PRAM computational model