×

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)
PDF BibTeX XML Cite
Full Text: DOI