19-09-2017, 09:38 AM
A tree T is tagged when n vertices are distinguished by names such as v / sub 1 /, v / sub 2 / ... v / sub n /. Two labeled trees are considered different if they have different vertex labels, although they may be isomorphic. According to the Cayley tree formula, there are trees n / sup n-2 / labeled on n vertices. Prufer used a simple way to test this formula and showed that there is a mapping between a tagged tree and a numeric sequence. From its test, we can find a naive sequential algorithm that transfers a tagged tree to a number sequence and vice versa. However, it is difficult to parallelize. In this paper we propose a parallel O (log n) algorithm for the construction of a tagged tree using the O (n) processors and the O (n log n) space in the EREW PRAM computational model.