Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, April 03, 2008, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Nicla Bernasconi

Quadratic exact-size and linear approximate-size random generation of planar graphs

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.

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