Generating Random Regular Graphs Quickly

A. Steger, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

137 Citations (Scopus)

Abstract

We present a practical algorithm for generating random regular graphs. For all d growing as a small power of n, the d-regular graphs on n vertices are generated approximately uniformly at random, in the sense that all d-regular graphs on n vertices have in the limit the same probability as n → ∞. The expected runtime for these ds is script O sign(nd2).

Original languageEnglish
Pages (from-to)377-396
Number of pages20
JournalCombinatorics Probability and Computing
Volume8
Issue number4
DOIs
Publication statusPublished - 1999
Externally publishedYes

Cite this