An Optimal Algorithm for Prufer Codes

Abstract Full-Text HTML Download Download as PDF (Size:150KB) PP. 111-115
DOI: 10.4236/jsea.2009.22016    6,682 Downloads   10,731 Views   Citations


This paper studies the algorithms for coding and decoding Prufer codes of a labeled tree. The algorithms for coding and decoding Prufer codes of a labeled tree in the literatures require time usually. Although there exist linear time algorithms for Prufer-like codes [1,2,3], the algorithms utilize the integer sorting algorithms. The special range of the integers to be sorted is utilized to obtain a linear time integer sorting algorithm. The Prufer code problem is reduced to integer sorting. In this paper we consider the Prufer code problem in a different angle and a more direct manner. We start from a naïve algorithm, then improved it gradually and finally we obtain a very practical linear time algorithm. The techniques we used in this paper are of interest in their own right.

Cite this paper

X. Wang, L. Wang and Y. Wu, "An Optimal Algorithm for Prufer Codes," Journal of Software Engineering and Applications, Vol. 2 No. 2, 2009, pp. 111-115. doi: 10.4236/jsea.2009.22016.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] [1] S. Caminiti, I. Finocchi, and R. Petreschi, “A unified approach to coding labeled trees,” in Proceedings of the 6th Latin American Symposium on Theoretical Infor-matics (LATIN’04), LNCS 2976, pp. 339-348, 2004.
[2] [2] S. Caminiti, I. Finocchi, and R. Petreschi, “On coding la- beled trees,” To appear on Theoretical Computer Sci-ence, 2006.
[3] [3] H. C. Chen and Y. L. Wang, “An efficient algorithm for generating Prufer codes from labeled trees,” Theory of Computing Systems, Vol. 33, pp. 97–105, 2000.
[4] [4] A. Cayley, “A theorem on trees,” Quarterly Journal of Mathematics, Vol. 23, pp. 376–378, 1889.
[5] [5] L. Devroye, “Non-uniform random variate generation,” Springer-Verlag, New York, Exercise 2, pp. 666, 1986.
[6] [6] A. Nijenhuis and H. S. Wilf, “Combinatorial algorithms for computers and calculators,” Second Editon, Academic Press, New York, Exercise 46, pp. 293, 1978.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.