A linear-time algorithm for the generation of trees

DOI10.1007/BF02522824MaRDI QIDQ675311zbMATHOpenAlexFDO

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

treesforestslinear-time algorithmrandom generationcoding

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

• scientific article; zbMATH DE number 3395910 (Why is no real title available?)
• A calculus for the random generation of labelled combinatorial structures
• A problem of arrangements
• 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

(31)

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

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)