An Optimal Algorithm for Prufer Codes
- 1
- 2
- 3
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.
- [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] S. Caminiti, I. Finocchi, and R. Petreschi, “On coding la- beled trees,” To appear on Theoretical Computer Sci-ence, 2006.
- [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] A. Cayley, “A theorem on trees,” Quarterly Journal of Mathematics, Vol. 23, pp. 376–378, 1889.
- [5] L. Devroye, “Non-uniform random variate generation,” Springer-Verlag, New York, Exercise 2, pp. 666, 1986.
- [6] A. Nijenhuis and H. S. Wilf, “Combinatorial algorithms for computers and calculators,” Second Editon, Academic Press, New York, Exercise 46, pp. 293, 1978.