# zbMATH — the first resource for mathematics

Generating random regular graphs quickly. (English) Zbl 0935.05082
Summary: 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\to\infty$$. The expected runtime for these $$d$$s is $$O(nd^2)$$.

##### MSC:
 05C80 Random graphs (graph-theoretic aspects)
##### Keywords:
random regular graphs; probability
Full Text: