Simulating Size-constrained Galton-Watson Trees

Authors: Luc Devroye - SIAM Journal on Computing 2012 cited by 30

We discuss various methods for generating random Galton–Watson trees conditional on their sizes being equal to n. A linear expected time algorithm is proposed.MSC codes65C1065C0511K4568U20Keywordsrandom variate generationCayley treesCatalan treessimulationGalton-Watson branching processexpected time analysisrandom trees