Simulating Size-constrained Galton–Watson Trees

DOI10.1137/090766632zbMath1243.65005OpenAlexW2046006541MaRDI QIDQ2884570

Luc P. Devroye

Publication date: 30 May 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090766632

zbMATH Keywords

simulationexpected time analysisrandom treesrandom variate generationgraphical examplesGalton-Watson branching processCayley treesCatalan trees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random number generation in numerical analysis (65C10) Pseudo-random numbers; Monte Carlo methods (11K45)

Related Items (9)

Root estimation in Galton–Watson trees ⋮ Exact-Size Sampling of Enriched Trees in Linear Time ⋮ Scaling limits of slim and fat trees ⋮ Models of random subtrees of a graph ⋮ On the maximal offspring in a subcritical branching process ⋮ Growing random uniform \(d\)-ary trees ⋮ Random-Bit Optimal Uniform Sampling for Rooted Planar Trees with Given Sequence of Degrees and Applications ⋮ Inference for conditioned Galton-Watson trees from their Harris path ⋮ Analysis of an efficient reduction algorithm for random regular expressions based on universality detection

This page was built for publication: Simulating Size-constrained Galton–Watson Trees