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
- Probability Inequalities for sums of Bounded Random Variables
- On the method of bounded differences
- The asymptotic number of labeled graphs with given degree sequences
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs
- Some problems in the enumeration of labelled graphs
- Uniform generation of random regular graphs of moderate degree
- Asymptotic enumeration by degree sequence of graphs with degreeso(n 1/2)
- Fast uniform generation of regular graphs
- Generating random regular graphs
- Random Graph Processes with Degree Restrictions