Generating graphs randomly

Speaker: 

Dr. Catherine Greenhill

Affiliation: 

University of New South Wales

Date: 

Tue, 01/03/2011 - 12:00pm to 1:00pm

Venue: 

RC-4082, Red Centre Building, UNSW

Abstract: 

The problem of generating a random element from the set of all labelled simple graphs with a given degree sequence has many applications. I will take a not-so-random walk through the history of this problem, from the configuration model of the late 1970s through to Bayati, Kim and Saberi's remarkable recent algorithm based on sequential importance sampling.

School Seminar Series: