Generating Random Regular Graphs Quickly
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 [rightward arrow] [infty infinity]. The expected runtime for these ds is [script O](nd2).(Received June 3 1998)
(Revised November 11 1998)
1 Research supported by the Australian Research Council.