TY - JOUR
T1 - Uniform generation of random regular graphs of moderate degree
AU - McKay, Brendan D.
AU - Wormald, Nicholas C.
PY - 1990
Y1 - 1990
N2 - We show how to generate k-regular graphs on n vertices uniformly at random in expected time O(nk3), provided k = O(n 1 3). The algorithm employs a modification of a switching argument previously used to count such graphs asymptotically for k = o(n 1 3). The asymptotic formula is re-derived, using the new switching argument. The method is applied also to graphs with given degree sequences, provided certain conditions are met. In particular, it applies if the maximum degree is O(∥E(G)∥ 1 4). The method is also applied to bipartite graphs.
AB - We show how to generate k-regular graphs on n vertices uniformly at random in expected time O(nk3), provided k = O(n 1 3). The algorithm employs a modification of a switching argument previously used to count such graphs asymptotically for k = o(n 1 3). The asymptotic formula is re-derived, using the new switching argument. The method is applied also to graphs with given degree sequences, provided certain conditions are met. In particular, it applies if the maximum degree is O(∥E(G)∥ 1 4). The method is also applied to bipartite graphs.
UR - http://www.scopus.com/inward/record.url?scp=0002511049&partnerID=8YFLogxK
U2 - 10.1016/0196-6774(90)90029-E
DO - 10.1016/0196-6774(90)90029-E
M3 - Article
AN - SCOPUS:0002511049
VL - 11
SP - 52
EP - 67
JO - Numerical Algorithms
JF - Numerical Algorithms
SN - 1017-1398
IS - 1
ER -