Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 17, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Eric Fusy (Ecole Polytechnique, Palaiseau Cedex)
The method of Boltzmann samplers is a new efficient framework for the random generation of combinatorial structures. Like another general framework for random generation called the recursive method, it can be applied on any combinatorial class having an explicit decomposition grammar. The main difference is that the recursive method works at fixed size and relies on the coefficients counting the objects of the class, whereas Boltzmann samplers can draw objects of any size and rely on the generating function associated with the class. We will explain how Boltzmann samplers can be simply assembled for structures specified with classical constructions such as disjoint union and cartesian product, and also more involved constructions like multiset. We will also point out the example of planar graphs, where the conjonction of Boltzmann samplers and of recent results of analytic and bijective combinatorics yields a linear time random generator for labeled planar graphs.
Automatic MiSe System Software Version 1.4803M | admin login