Article ID Journal Published Year Pages File Type
420074 Discrete Applied Mathematics 2012 10 Pages PDF
Abstract

In the framework of analytic combinatorics, Boltzmann models give rise to efficient algorithms for the random generation of combinatorial objects. This paper proposes an efficient Boltzmann sampler for ordered structures defined by first-order differential specifications. Under an abstract real-arithmetic computation model, our algorithm is of linear complexity for free generation; in addition, for many classical structures, the complexity is also linear when a small tolerance is allowed on the size of the generated object. The resulting implementation makes it possible to generate very large random objects, such as increasing trees, in a few seconds on a standard machine.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,