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
SN - 0196-6774
VL - 11
SP - 52
EP - 67
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -