Uniform generation of forests of restricted height

DOI10.1016/0020-0190(94)00054-9MaRDI QIDQ1330666zbMATH OpenOpenAlexWikidataFDO

Authors Michael D. Atkinson, Jörg-Rüdiger Sack

Publication date 21 July 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)00054-9

zbMATH Keywords

analysis of algorithmsdesign of algorithmsforestsinformation storagerandom generationtrees

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Review text

Tree structures occur throughout the theory of information storage. Typically each tree node contains some data information and some pointers to other tree nodes. In most cases the number \(k\) of pointer fields is fixed and the structure is referred to as a \(k\)-way tree. More formally, a \(k\)-way tree can be defined as being either empty (having no nodes) or as consisting of a root node together with an ordered sequence of \(k\) \(k\)-way trees. For developing and testing algorithms which manipulate forests it is useful to have methods for generating them in a uniform manner (so that each forest is generated with the same probability). Many methods have been given in the case of binary trees (2-way trees with one component). Some of these methods extend to \(k\)-way trees but there has been little previous work on uniformly generating trees of a fixed or bounded height. This paper considers \(k\)-way forests of fixed size \(n\), height \(h\), and number of components \(c\). A generator is given for producing such forests uniformly at random thereby answering an open problem posed by Lee, Lee, and Wong. Each random forest is generated in a linear number of operations in its size. The algorithm computes a table of values in a pre-processing phase. This table occupies \(O(hn^ 2)\) locations and takes \(O(hn^ 3)\) time to produce.

Recommendations

• A linear-time algorithm for the generation of trees
• Uniform Generation of Rooted Ordered Trees with Prescribed Degrees
• The generation of binary trees as a numerical problem
• Fast random generation of binary, t-ary and other types of trees
• Enumerating k-way trees

Cites work

• A method and two algorithms on the theory of partitions
• Counting and randomly generating binary trees
• Generating binary trees at random
• Generating binary trees of bounded height
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• On Random Binary Trees
• The average height of binary trees and other simple trees
• The generation of binary trees as a numerical problem
• Uniform Random Generation of Strings in a Context-Free Language

Cited in

(4)

• Enumerating k-way trees
• A workbench for computational geometry
• Uniformly Discrete Forests with Poor Visibility
• Algorithms and Computation

This page was built for publication: Uniform generation of forests of restricted height

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1330666)