An Optimal Algorithm for Prufer Codes

Xiaodong Wang, Lei Wang, Yingjie Wu
DOI: 10.4236/jsea.2009.22016                

Abstract

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.

Keywords

Design of Algorithm, Labeled Trees, Prufer Codes, Integer Sorting

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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.