Exact-Size Sampling of Enriched Trees in Linear Time

DOI10.1137/21M1459733MaRDI QIDQ6057780zbMATH OpenOpenAlexFDO

Authors Konstantinos Panagiotou, Leon Ramzews, Benedikt Stufler

Publication date 26 October 2023

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

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

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)

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.

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

Cites work

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

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)