Uniform generation of random regular graphs

Research output: Contribution to journalArticleResearchpeer-review

13 Citations (Scopus)

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(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 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).

Original languageEnglish
Pages (from-to)1395-1427
Number of pages33
JournalSIAM Journal on Computing
Volume46
Issue number4
DOIs
Publication statusPublished - 2017

Keywords

  • Markov chain
  • Regular graphs
  • Switching
  • Uniform generation

Cite this