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 time, processor EREW-PRAM algorithm for determining the Prüfer code of an n-node labeled chain and an 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. (IEEE Trans. Parallel Distributed Systems 8 (12) (1997) 1236–1240).
Computing Prüfer codes efficiently in parallel / Greenlaw, R.; Petreschi, Rossella. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 102:(2000), pp. 205-222. [10.1016/S0166-218X(99)00221-8]
Computing Prüfer codes efficiently in parallel
PETRESCHI, Rossella
2000
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 time, processor EREW-PRAM algorithm for determining the Prüfer code of an n-node labeled chain and an 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. (IEEE Trans. Parallel Distributed Systems 8 (12) (1997) 1236–1240).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
