Exact-Size Sampling of Enriched Trees in Linear Time
From MaRDI portal
Publication:6057780
DOI10.1137/21m1459733zbMath1526.60003arXiv2110.11472OpenAlexW3209891732MaRDI QIDQ6057780
Benedikt Stufler, Konstantinos D. Panagiotou, Leon Ramzews
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
Random graphs (graph-theoretic aspects) (05C80) Computational methods for problems pertaining to probability theory (60-08) Combinatorics in computer science (68R05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum degree in minor-closed classes of graphs
- Scaling limits of random graphs from subcritical classes
- Asymptotics and random sampling for BCI and BCK lambda terms
- Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
- Invariance principles for Galton-Watson trees conditioned on the number of leaves
- Algorithms for combinatorial structures: well-founded systems and Newton iterations
- An algorithm computing combinatorial specifications of permutation classes
- The cycle lemma and some applications
- A decorated tree approach to random permutations in substitution-closed classes
- A complete grammar for decomposing a family of graphs into 3-connected components
- Uniform random generation of decomposable structures using floating-point arithmetic
- Schröder parenthesizations and chordates
- A calculus for the random generation of labelled combinatorial structures
- Random enriched trees with applications to random graphs
- Boltzmann samplers for first-order differential specifications
- Limits of random tree-like discrete structures
- Universal limits of substitution-closed permutation classes
- Counting phylogenetic networks of level 1 and 2
- 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 outerplanar maps with independent link-weights
- Scaling limits of random Pólya trees
- Simple permutations and pattern restricted permutations
- Simulating Size-constrained Galton–Watson Trees
- Random non-crossing plane configurations: A conditioned Galton-Watson tree approach
- Uniform random sampling of planar graphs in linear time
- Boltzmann Samplers, Pólya Theory, and Cycle Pointing
- Asymptotic Study of Subcritical Graph Classes
- Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation
- The Degree Sequence of Random Graphs from Subcritical Classes
- Random Sampling of Plane Partitions
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Boltzmann Sampling of Unlabelled Structures
- Extremal Parameters in Sub-Critical Graph Classes
- Polynomial tuning of multiparametric combinatorial samplers
- Split-Decomposition Trees with Prime Nodes: Enumeration and Random Generation of Cactus Graphs
- Generating Outerplanar Graphs Uniformly at Random
- A branching process approach to level‐k phylogenetic networks
- Graphon convergence of random cographs
This page was built for publication: Exact-Size Sampling of Enriched Trees in Linear Time
