Linear time tree codes
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.
- A method for the linear recording of graphs
- A new algorithm for solving the tree isomorphism problem
- An Optimal Diagonal Tree Code
- Constant Time Generation of Rooted Trees
- Diagonal tree codes
- Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
- Generating Trees and Other Combinatorial Objects Lexicographically
- scientific article; zbMATH DE number 3679848 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3575612 (Why is no real title available?)
- scientific article; zbMATH DE number 3307338 (Why is no real title available?)
- scientific article; zbMATH DE number 3390780 (Why is no real title available?)
- Lexicographic generation of ordered trees
- The distance matrix of a graph and its tree realization
- The distribution of degrees in a large random tree
- Computing the characteristic polynomial of a tree
- Uniform random generation of expressions respecting algebraic identities
- Encoding trees by linear recurrence sequences
- A note on trees and codes
- Linear-time algorithms for encoding trees as sequences of node labels
- scientific article; zbMATH DE number 568780 (Why is no real title available?)
- Universal coding of integers and unbounded search trees
- On the reconstruction of a Motzkin Tree from its code
- scientific article; zbMATH DE number 1744078 (Why is no real title available?)
- scientific article; zbMATH DE number 743588 (Why is no real title available?)
- scientific article; zbMATH DE number 861317 (Why is no real title available?)
- Data coding by linear forms of numerical sequences
- Computing and Combinatorics
- Bijective linear time coding and decoding for \(k\)-trees
This page was built for publication: Linear time tree codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799118)
