Goal:


I want to generate a r-regular graph with n vertices. rn = 2m.


Current best:



```
(1) take n vertices; randomly pick a vertex v of degree < r.
(2) S = set of all vertices of degree < r, and not a neighbor of v.
(3) create an edge between v and a random element of S.
(4) repeat.

```

Question:


Is there a more parallel way to do this?


Clarification:


Suppose I wanted to randomly pick an element in [1...n].
 I could do it sequentially like:



```
take 1 w/ prob 1/n
else take 2 w/ prob 1/n-1
else take 3 w/ prob 1/n-2
...

```

Or I could do it "one shot" by generating a random element between [1...n].


Similarly, I want to generate a r-regular graph "one shot" rather than an single edge at a time.


Goal:


This is to build mental intuition of what it means to "uniformly pick a r-regular graph."


Thanks!



Generating r-Regular Random Graph in Parallel
This question is more difficult that it seems.


Firstly, there is a difference between picking edges of a graph uniformly, and picking a $r$-regular graph uniformly.


Let $G\_{r,n}$ be the set of $r$-regular graphs on $n$ nodes. By "uniformly pick a $r$-regular graph", you need to create an algorithm that chooses $G \in G\_{r,n}$ with probability $1/|G\_{r,n}|$. There are probabilistic methods to do this, perhaps they even lend themselves to parallelization. 


See the section on algorithms for generation of random regular graphs [here](http://en.wikipedia.org/wiki/Random_regular_graph).
In particular,B. McKay and N. Wormald, [Uniform Generation of Random Regular Graphs of Moderate Degree,](http://cs.anu.edu.au/~bdm/papers/RandRegGen.pdf) Journal of Algorithms, Vol. 11 (1990), pp 52-67


