An Efficient Algorithm for Generating Prüfer Codes from Labelled Trees |
| |
Authors: | H -C Chen Y -L Wang |
| |
Affiliation: | (1) Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, Republic of China ylwang@cs.ntust.edu.tw, TW |
| |
Abstract: | According to Cayley's tree formula, there are n
n-2
labelled trees on n vertices. Prüfer gave a bijection between the set of labelled trees on n vertices and sequences of n-2 numbers, each in the range 1, 2, ..., n . Such a number sequence is called a Prüfer code. The straightforward implementation of his bijection takes O(n log n ) time. In this paper we propose an O(n) time algorithm for the same problem. Our algorithm can be easily parallelized so that a Prüfer code can be generated in
O (log n ) time using O(n) processors on the EREW PRAM computational model.
Received October 2, 1998, and in final form March 1, 1999. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|