Generating random regular graphs
Jeong Han Kim, Van H. Vu · ACM Symposium on Theory of Computing (STOC) · 2003
Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [9] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d=O(n1/3-e), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd2). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author.Besides being perhaps the only algorithm which works for relatively large d in practical time, our result also has a significant theoretical value, as it can be used to derive many properties of uniform random regular graphs.
Cited by 97 works. doi:10.1145/780542.780576
Authors
References
- The asymptotic number of labeled graphs with given degree sequences
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs
- Models of Random Regular 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
- A proof of alon's second eigenvalue conjecture
- Concentration of Multivariate Polynomials and Its Applications
- Random Graph Processes with Degree Restrictions
- Generating Random Regular Graphs Quickly