A tree T is labeled when the n vertices are distinguished from one another by names such as v/sub 1/, v/sub 2/...v/sub 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/sup 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.
展开▼
机译：当通过诸如v / sub 1 /，v / sub 2 / ... v / sub n /之类的名称区分n个顶点时，树T被标记。如果两个标记的树具有不同的顶点标记，即使它们是同构的，也被认为是不同的。根据Cayley的树公式，在n个顶点上有n / s n-2 /个标记树。 Prufer使用一种简单的方法来证明该公式，并证明了在标记的树和数字序列之间存在映射。从他的证明中，我们可以找到一个幼稚的顺序算法，该算法将标记的树转换为数字序列，反之亦然。但是，很难并行化。在本文中，我们将提出一种O（log n）时间并行算法，通过在EREW PRAM计算模型上使用O（n）处理器和O（n log n）空间来构造标记树。
展开▼
