Linear time tree codes (Q799118): Difference between revisions

This paper deals with a new method of coding unlabeled trees into strings of integers. For a tree of n vertices coding as well as decoding need time O(n). Computer experiments show that for given \(n\leq 20\), the ''mean length'' of the code strings is shorter than with the Walk-around-code [\textit{R. C. Read}, Graph Theory Comput., 153-182 (1972; Zbl 0247.05104)] or with the Diagonal-code [\textit{A. K. Dewdney}, Inf. Control 40, 234-239 (1979; Zbl 0398.05028)]. This result is shown to be valid asymptotically for a slight modification of the method. The new method is used to derive an algorithm for generating all unlabeled trees of a given size without repetition.