Computing Prüfer codes efficiently in parallel

Computing Prüfer codes efficiently in parallel

0.00 Avg rating0 Votes
Article ID: iaor2002338
Country: Netherlands
Volume: 102
Issue: 3
Start Page Number: 205
End Page Number: 222
Publication Date: Jun 2000
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: minimum spanning trees
Abstract:

A Prüfer 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 into the ith position of the sequence, and then delete the leaf. Prüfer codes provide an alternative to the usual representation of trees. We present an optimal O(logn) time, n/logn processor EREW-PRAM algorithm for determining the Prüfer code for an n-node labeled chain and an O(logn) time, n processor EREW-PRAM algorithm for constructing the Prüfer code of an n-node labeled free tree. This resolves an open question posed by Wang et al.

Reviews

Required fields are marked *. Your email address will not be published.