Generating random regular graphs quickly

被引：158

作者：

Steger, A ^{[1
]}

Wormald, NC

机构：

[1] Tech Univ Munich, Inst Informat, D-80290 Munich, Germany

[2] Univ Melbourne, Dept Math & Stat, Parkville, Vic 3052, Australia

来源：

COMBINATORICS PROBABILITY & COMPUTING | 1999年 / 8卷 / 04期

关键词：

D O I：

10.1017/S0963548399003867

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 --> infinity. The expected runtime for these ds is O(nd(2)).

引用

页码：377 / 396

页数：20

共 12 条

[1] ASYMPTOTIC NUMBER OF LABELED GRAPHS WITH GIVEN DEGREE SEQUENCES [J].

BENDER, EA ;

CANFIELD, ER .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 24 (03) :296-307

[2]

Bollobas B, 1980, EUR J COMBINAT, V1, P311

[3] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES [J].

HOEFFDING, W .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) :13-+

[4] FAST UNIFORM GENERATION OF REGULAR GRAPHS [J].

JERRUM, M ;

SINCLAIR, A .

THEORETICAL COMPUTER SCIENCE, 1990, 73 (01) :91-100

[5]

MCDIARMID C, 1989, LOND MATH S, V141, P148

[6] ASYMPTOTIC ENUMERATION BY DEGREE SEQUENCE OF GRAPHS WITH DEGREES O(N1/2) [J].

MCKAY, BD ;

WORMALD, NC .

COMBINATORICA, 1991, 11 (04) :369-382

[7] UNIFORM GENERATION OF RANDOM REGULAR GRAPHS OF MODERATE DEGREE [J].

MCKAY, BD ;

WORMALD, NC .

JOURNAL OF ALGORITHMS, 1990, 11 (01) :52-67

[8]

MCKAY BD, 1985, ARS COMBINATORIA, V19A, P15

[9]

RUCINSKI A, 1992, COMBINATORICS PROBAB, V1, P169

[10]

Tinhofer G., 1979, APPL COMPUTER SCI BE, V13, P265

← 1 2 →