Generating Random Regular Graphs Quickly

Angelika Steger, N. C. Wormald · Combinatorics Probability Computing · 1999

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 [Oscr ](nd2).

Cited by 234 works. doi:10.1017/s0963548399003867

Authors

References