A linear-time algorithm for the generation of trees

DOI10.1007/BF02522824MaRDI QIDQ675311zbMATH OpenOpenAlexFDO

Authors L. Alonso, R. Schott, J. L. Rémy

Publication date 6 March 1997

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02522824

zbMATH Keywords

codingforestslinear-time algorithmrandom generationtrees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Fast random generation of binary, t-ary and other types of trees
• Generating random binary trees -- a survey
• Uniform Generation of Rooted Ordered Trees with Prescribed Degrees
• Random generation of colored trees
• Generating binary trees at random

Cites work

• A calculus for the random generation of labelled combinatorial structures
• A problem of arrangements
• scientific article; zbMATH DE number 3395910 (Why is no real title available?)
• On context-free languages and push-down automata
• Patterns in trees
• The cycle lemma and some applications
• Uniform generation of a Motzkin word

Cited in

(37)

• Generating binary trees of bounded height
• Generating binary trees at random
• A linear-time algorithm for the feasibility of pebble motion on trees
• Random generation of trees and other combinatorial objects
• Uniform random generation of decomposable structures using floating-point arithmetic
• Uniform generation of forests of restricted height
• Linear-time construction of treaps and Cartesian trees
• Uniform generation of a Motzkin word
• Generating random binary trees -- a survey
• Efficient random sampling of binary and unary-binary trees via holonomic equations
• Growing random uniform d-ary trees
• Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and applications
• Uniform generation of a Schröder tree
• scientific article; zbMATH DE number 434865 (Why is no real title available?)
• Uniform Generation of Rooted Ordered Trees with Prescribed Degrees
• scientific article; zbMATH DE number 6622715 (Why is no real title available?)
• Generating rooted trees of m nodes uniformly at random
• Uniformly random tree generation
• scientific article; zbMATH DE number 4091527 (Why is no real title available?)
• scientific article; zbMATH DE number 700567 (Why is no real title available?)
• A Comparison of Random Binary Tree Generators
• A linear algorithm for compact box-drawings of trees
• Constant Time Generation of Free Trees
• scientific article; zbMATH DE number 6123089 (Why is no real title available?)
• Linear-time algorithm for sliding tokens on trees
• A linear time algorithm for the feasibility of pebble motion on trees
• Random generation of colored trees
• Linear-time generation of inhomogeneous random directed walks
• Graph-Theoretic Concepts in Computer Science
• Fast random generation of binary, t-ary and other types of trees
• Fast generation of unlabelled free trees using weight sequences
• Growing uniform planar maps face by face
• Slit-slide-sew bijections for constellations and quasiconstellations
• Simple random sampling of binary forests with fixed number of nodes and trees
• Simple random sampling of binary forests with fixed number of nodes and trees
• Generating binary trees with uniform probability
• Linear time tree codes

This page was built for publication: A linear-time algorithm for the generation of trees

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