A linear-time algorithm for the generation of trees

DOI10.1007/BF02522824zbMATH Open0865.68088OpenAlexW1971148082MaRDI QIDQ675311FDOQ675311

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

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

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)

Cites Work

• A problem of arrangements
• Uniform generation of a Motzkin word
• Patterns in trees
• A calculus for the random generation of labelled combinatorial structures
• On context-free languages and push-down automata
• The cycle lemma and some applications
• Title not available (Why is that?)

Cited In (31)

• A linear time algorithm for the feasibility of pebble motion on trees
• Title not available (Why is that?)
• Linear-time construction of treaps and Cartesian trees
• A linear algorithm for compact box-drawings of trees
• Uniform random generation of decomposable structures using floating-point arithmetic
• Constant Time Generation of Free Trees
• Generating random binary trees -- a survey
• Random generation of colored trees
• A linear-time algorithm for the feasibility of pebble motion on trees
• Growing random uniform \(d\)-ary trees
• 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
• Generating binary trees at random
• Generating rooted trees of \(m\) nodes uniformly at random
• Uniform generation of a Motzkin word
• Uniform generation of a Schröder tree
• Title not available (Why is that?)
• Generating binary trees with uniform probability
• Uniform generation of forests of restricted height
• Uniform Generation of Rooted Ordered Trees with Prescribed Degrees
• Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and applications
• Linear-time algorithm for sliding tokens on trees
• A Comparison of Random Binary Tree Generators
• Title not available (Why is that?)
• Linear-time generation of inhomogeneous random directed walks
• Title not available (Why is that?)
• Linear time tree codes
• Efficient random sampling of binary and unary-binary trees via holonomic equations
• Graph-Theoretic Concepts in Computer Science
• Generating binary trees of bounded height

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)