UNIFORM GENERATION OF RANDOM REGULAR GRAPHS OF MODERATE DEGREE

被引：91

作者：

MCKAY, BD

WORMALD, NC

机构：

[1] AUSTRALIAN NATL UNIV,DEPT COMP SCI,CANBERRA,ACT 2601,AUSTRALIA

[2] UNIV AUCKLAND,DEPT MATH & STAT,AUCKLAND,NEW ZEALAND

来源：

JOURNAL OF ALGORITHMS | 1990年 / 11卷 / 01期

关键词：

D O I：

10.1016/0196-6774(90)90029-E

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. © 1990.

引用

页码：52 / 67

页数：16