Abstract
We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for d-regular graphs. REG can be implemented such that each graph is generated in expected time O(nd^3), provided that d=o(n^{1/2}). Our result significantly improves the previously best uniform sampler, which works efficiently only when d=O(n^{1/3}), with essentially the same running time for the same d. We also give a linear-time approximate sampler REG*, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d=o(n^{1/2}). If time permits, I will describe how to use this new method to generate uniformly random graphs with power-law (with exponent below 3) degree sequences.Time
2016-11-16 10:00 ~ 11:00Speaker
Jane Gao , Monash University
Room
Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics
