Linear time tree codes
type: Item
instance of: scholarly article
title: Linear time tree codes
zbMATH Open document ID: 0547.68065
DOI: 10.1007/BF02242268
author: H. Schreck
author: Gottfried Tinhofer
published in: Computing
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3872700
zbMATH Keywords: tree codes
zbMATH Keywords: generation of trees
zbMATH Keywords: coding unlabeled trees into strings of integers
zbMATH Keywords: algorithm
MaRDI profile type: Publication
cites work: Q4091421
cites work: Constant Time Generation of Rooted Trees
cites work: An Optimal Diagonal Tree Code
cites work: Diagonal tree codes
cites work: Q3875946
cites work: Q4148000
cites work: A new algorithm for solving the tree isomorphism problem
cites work: The distance matrix of a graph and its tree realization
cites work: Q5588439
cites work: Q5659553
cites work: Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
cites work: The distribution of degrees in a large random tree
cites work: A method for the linear recording of graphs
cites work: Generating Trees and Other Combinatorial Objects Lexicographically
cites work: Lexicographic generation of ordered trees
full work available at URL: https://doi.org/10.1007/bf02242268
OpenAlex ID: W43233584
description: scientific article; zbMATH DE number 3872700