Random-Bit Optimal Uniform Sampling for Rooted Planar Trees with Given Sequence of Degrees and Applications
From MaRDI portal
Publication:2795938
DOI10.1007/978-3-319-29221-2_9zbMath1437.68136arXiv1401.4712OpenAlexW1495016581MaRDI QIDQ2795938
Julien David, Olivier Bodini, Philippe Marchal
Publication date: 23 March 2016
Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1401.4712
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (3)
Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers ⋮ Efficient random sampling of binary and unary-binary trees via holonomic equations ⋮ Bijections between Łukasiewicz walks and generalized tandem walks
Cites Work
- Uniform generation of a Schröder tree
- The stable trees are nested
- A linear-time algorithm for the generation of trees
- Controlled non-uniform random generation of decomposable structures
- A calculus for the random generation of labelled combinatorial structures
- A limit theorem for the contour process of conditioned Galton-Watson trees
- Boltzmann samplers for first-order differential specifications
- The continuum random tree. III
- Efficient random sampling of binary and unary-binary trees via holonomic equations
- Simulating Size-constrained Galton–Watson Trees
- An Efficient Method for Generating Discrete Random Variables with General Distributions
- Interval algorithm for random number generation
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- The Number of Planted Plane Trees with a Given Partition
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Random-Bit Optimal Uniform Sampling for Rooted Planar Trees with Given Sequence of Degrees and Applications