Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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)

Random generation of combinatorial structures using Boltzmann samplers

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login