Uniform generation of random regular graphs

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

5 Citations (Scopus)

Abstract

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 languageEnglish
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015)
PublisherIEEE Computer Society
Pages1218-1230
Number of pages13
ISBN (Electronic)9781467381918
DOIs
Publication statusPublished - 11 Dec 2015
EventIEEE Symposium on Foundations of Computer Science 2015 - DoubleTree Hotel at the Berkeley Marina, Berkeley, United States of America
Duration: 17 Oct 201520 Oct 2015
Conference number: 56th

Conference

ConferenceIEEE Symposium on Foundations of Computer Science 2015
Abbreviated titleFOCS 2015
CountryUnited States of America
CityBerkeley
Period17/10/1520/10/15

Keywords

  • Markov chain
  • regular graphs
  • switching
  • uniform generation

Cite this