A linear-time algorithm for the generation of trees

DOI10.1007/BF02522824zbMath0865.68088OpenAlexW1971148082MaRDI QIDQ675311

Laurent Alonso, René Schott, Jean-Luc 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

treescodingrandom generationforestslinear-time algorithm

Mathematics Subject Classification ID

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

Related Items (8)

Uniform generation of a Schröder tree ⋮ Uniform generation of a Motzkin word ⋮ Efficient random sampling of binary and unary-binary trees via holonomic equations ⋮ Random generation of colored trees ⋮ Growing uniform planar maps face by face ⋮ Random-Bit Optimal Uniform Sampling for Rooted Planar Trees with Given Sequence of Degrees and Applications ⋮ Generating random binary trees -- a survey ⋮ Uniform random generation of decomposable structures using floating-point arithmetic

Cites Work

• Unnamed Item
• The cycle lemma and some applications
• A calculus for the random generation of labelled combinatorial structures
• Uniform generation of a Motzkin word
• Patterns in trees
• A problem of arrangements
• On context-free languages and push-down automata

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