Linear time tree codes (Q799118)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3872700
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Linear time tree codes |
scientific article; zbMATH DE number 3872700 |
Statements
Linear time tree codes (English)
0 references
1984
0 references
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.
0 references
tree codes
0 references
generation of trees
0 references
coding unlabeled trees into strings of integers
0 references
algorithm
0 references
0 references
0.8626723885536194
0 references
0.8594968318939209
0 references
0.8510943651199341
0 references
0.8220553994178772
0 references
0.8170735239982605
0 references
