Exact-Size Sampling of Enriched Trees in Linear Time

DOI10.1137/21M1459733zbMATH Open1526.60003arXiv2110.11472OpenAlexW3209891732MaRDI QIDQ6057780FDOQ6057780

Authors: Konstantinos Panagiotou, Leon Ramzews, Benedikt Stufler 

Publication date: 26 October 2023

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

Abstract: Various combinatorial classes such as outerplanar graphs and maps, series-parallel graphs, substitution-closed classes of permutations and many more allow bijective encodings by so-called enriched trees, which are rooted trees with additional structure on the offspring of each node. Using this universal description we develop sampling procedures that uniformly generate objects from this classes with a given size $n$ in expected time $O(n)$.The key ingredient is a representation of enriched trees in terms of decorated Bienaym'e--Galton--Watson trees, which allows us to develop a novel combination of Devroye's efficient sampler for trees (Devroye, 2012) with Boltzmann sampling techniques. Additionally, we construct expected linear time samplers for critical Bienaym'e--Galton--Watson trees having exactly $n$ (out of $gen$ total) nodes with outdegree in some fixed set, enabling uniform generation for many combinatorial classes such as dissections of polygons.

Full work available at URL: https://arxiv.org/abs/2110.11472

Recommendations

• Exact-size sampling for Motzkin trees in linear time via Boltzmann samplers and holonomic specification
• Uniform random sampling of planar graphs in linear time
• Boltzmann sampling of unlabelled structures
• Boltzmann sampling of ordered structures
• scientific article; zbMATH DE number 5050599

zbMATH Keywords

random graphsGalton-Watson treesBoltzmann samplingexact-size sampling

Mathematics Subject Classification ID

Computational methods for problems pertaining to probability theory (60-08) Random graphs (graph-theoretic aspects) (05C80) Combinatorics in computer science (68R05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Analytic combinatorics
• A complete grammar for decomposing a family of graphs into 3-connected components
• Asymptotic study of subcritical graph classes
• The degree sequence of random graphs from subcritical classes
• Title not available (Why is that?)
• Extremal Parameters in Sub-Critical Graph Classes
• Maximum degree in minor-closed classes of graphs
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Scaling limits of random graphs from subcritical classes
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• A calculus for the random generation of labelled combinatorial structures
• Uniform random generation of decomposable structures using floating-point arithmetic
• Schröder parenthesizations and chordates
• Boltzmann samplers for first-order differential specifications
• Multi-dimensional Boltzmann sampling of languages
• Boltzmann Samplers, Pólya Theory, and Cycle Pointing
• Random Sampling of Plane Partitions
• Asymptotics and random sampling for BCI and BCK lambda terms
• Boltzmann sampling of unlabelled structures
• Simple permutations and pattern restricted permutations
• Maximal biconnected subgraphs of random planar graphs
• Uniform random sampling of planar graphs in linear time
• Random non-crossing plane configurations: a conditioned Galton-Watson tree approach
• Invariance principles for Galton-Watson trees conditioned on the number of leaves
• Algorithms for combinatorial structures: well-founded systems and Newton iterations
• Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation
• An algorithm computing combinatorial specifications of permutation classes
• The cycle lemma and some applications
• Scaling limits of random Pólya trees
• Split-decomposition trees with prime nodes: enumeration and random generation of cactus graphs
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• Random enriched trees with applications to random graphs
• Limits of random tree-like discrete structures
• A decorated tree approach to random permutations in substitution-closed classes
• Universal limits of substitution-closed permutation classes
• Generating Outerplanar Graphs Uniformly at Random
• A branching process approach to level‐k phylogenetic networks
• Graphon convergence of random cographs
• Counting phylogenetic networks of level 1 and 2
• Simulating size-constrained Galton-Watson trees
• Polynomial tuning of multiparametric combinatorial samplers
• Scaling limits of random outerplanar maps with independent link-weights

Cited In (1)

• Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions

This page was built for publication: Exact-Size Sampling of Enriched Trees in Linear Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057780)