Boltzmann Samplers for the Random Generation of Combinatorial Structures

363 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Scaling Limits of Random Graphs from Subcritical Classes (2014, methodology): “solutions. 3.6. Boltzmann Samplers. Boltzmann samplers provide a method of generating eciently random discrete combinatorial objects. They were introduced in Duchon, Flajolet, Louchard, and Schaeer [19] and were developed further in Flajolet, Fusy and Pivoteau [22]. Following these sources we will b”
Universal limits of substitution-closed permutation classes (2017, methodology): “ in substitutionclosed classes shown on Fig. 3 have been obtained through a Boltzmann sampler. Obtaining such a sampler is routine from the equations on the generating series given in Proposition 4.1 [27]. The only input that we need is a Boltzmann sampler for the set Sof simple permutations in the ”
Analytic Combinatorics (2009, background): “It also implies that, given a un iform random generator for G–objects, one can generate a random F–object of sizen in O(n) steps on average [177].”