<div class="csl-bib-body">
<div class="csl-entry">Panagiotou, K., Ramzews, L., & Stufler, B. (2023). Exact-Size Sampling of Enriched Trees in Linear Time. <i>SIAM Journal on Computing</i>, <i>52</i>(5), 1097–1131. https://doi.org/10.1137/21M1459733</div>
</div>
-
dc.identifier.issn
0097-5397
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/192047
-
dc.description.abstract
We create a novel connection between Boltzmann sampling methods and Devroye's algorithm to develop highly efficient sampling procedures that generate objects from important combinatorial classes with a given size n in expected time O(n). This performance is best possible and significantly improves the state of the art for samplers of subcritical graph classes (such as cactus graphs, outerplanar graphs, and series-parallel graphs), subcritical substitution-closed classes of permutations, Bienaymé-Galton-Watson trees conditioned on their number of leaves, and several further examples. Our approach allows for this high level of universality, as it applies in general to classes admitting bijective encodings by so-called enriched trees, which are rooted trees with additional structures on the offspring of each node.
en
dc.language.iso
en
-
dc.publisher
SIAM PUBLICATIONS
-
dc.relation.ispartof
SIAM Journal on Computing
-
dc.subject
Boltzmann sampling
en
dc.subject
exact-size sampling
en
dc.subject
Galton-Watson trees
en
dc.subject
random graphs
en
dc.title
Exact-Size Sampling of Enriched Trees in Linear Time