Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 03, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Nicla Bernasconi
I will present the main idea of the paper of Éric Fusy "Quadratic exact-size and linear approximate-size random generation of planar graphs" which introduces a new algorithm for the random generation of labelled planar graphs. Its principle rely on Boltzmann samplers as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. The paper combines the Boltzmann framework and a combinatorial bijection found by Fusy, Poulalhon and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Giménez and Noy.
I will introduce the Boltzmann Model and show how to exploit it to define an exact-size uniform sampler for planar graphs on n vertices. One can in this way easily obtain a running time of O(n^4.5) which already improves the best previously known time complexity, which was a little over O(n^7).
If time permits I will also give some hints on how one can achieve linear/quadratic running time for the approximate/exact-size generation of planar graphs.
Automatic MiSe System Software Version 1.4803M | admin login