Research output per year
Research output per year
Pu Gao, Nicholas Wormald
Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other › peer-review
We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler A for d-regular graphs. A can be implemented such that each graph is generated in expected time O(nd3), provided that d = o (√n). Our result significantly improves the previously best uniform sampler, which works efficiently only when d = O(n1/3), with essentially the same running time for the same d. We also give a linear-time approximate sampler B, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d = o(√n).
Original language | English |
---|---|
Title of host publication | Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015) |
Publisher | IEEE Computer Society |
Pages | 1218-1230 |
Number of pages | 13 |
ISBN (Electronic) | 9781467381918 |
DOIs | |
Publication status | Published - 11 Dec 2015 |
Event | IEEE Symposium on Foundations of Computer Science 2015 - DoubleTree Hotel at the Berkeley Marina, Berkeley, United States of America Duration: 17 Oct 2015 → 20 Oct 2015 Conference number: 56th |
Conference | IEEE Symposium on Foundations of Computer Science 2015 |
---|---|
Abbreviated title | FOCS 2015 |
Country/Territory | United States of America |
City | Berkeley |
Period | 17/10/15 → 20/10/15 |
Research output: Contribution to journal › Article › Research › peer-review