On the critical value for 'percolation' of minimum-weight trees in the mean-field distance model

被引：5

作者：

Aldous, D ^{[1
]}

机构：

[1] Univ Calif Berkeley, Dept Stat, Berkeley, CA 94720 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 1998年 / 7卷 / 01期

关键词：

D O I：

10.1017/S0963548397003155

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Consider the complete n-graph with independent exponential (mean n) edge-weights. Let M(c, n) be the maximal size of subtree for which the average edge-weight is at most c. It is shown that M(c, n) makes the transition from o(n) to Omega(n) around some critical value c(0), which can be specified in terms of a fixed point of a mapping on probability distributions.

引用

页码：1 / 10

页数：10

共 13 条

[1] ASYMPTOTICS IN THE RANDOM ASSIGNMENT PROBLEM [J].

ALDOUS, D .

PROBABILITY THEORY AND RELATED FIELDS, 1992, 93 (04) :507-534

[2]

Aldous D., 1990, RANDOM STRUCT ALGOR, DOI [10.1002/rsa.3240010402, DOI 10.1002/RSA.3240010402]

[3]

ALDOUS D, 1983, PROBABILITY STAT ANA, P1

[4]

Aldous David, 1992, COMB PROBAB COMPUT, V1, P281

[5]

ALDOUS DJ, 1997, 481 U C BERK STAT DE

[6] THE GROWTH AND SPREAD OF THE GENERAL BRANCHING RANDOM WALK [J].

Biggins, J. D. .

ANNALS OF APPLIED PROBABILITY, 1995, 5 (04) :1008-1024

[7] ON THE VALUE OF A RANDOM MINIMUM SPANNING TREE PROBLEM [J].

FRIEZE, AM .

DISCRETE APPLIED MATHEMATICS, 1985, 10 (01) :47-56

[8] THE BIRTH OF THE GIANT COMPONENT [J].

JANSON, S ;

KNUTH, DE ;

LUCZAK, T ;

PITTEL, B .

RANDOM STRUCTURES & ALGORITHMS, 1993, 4 (03) :233-358

[9] HIGHER-ORDER LINDLEY EQUATIONS [J].

KARPELEVICH, FI ;

KELBERT, MY ;

SUHOV, YM .

STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 1994, 53 (01) :65-96

[10] 1ST BIRTH PROBLEM FOR AN AGE-DEPENDENT BRANCHING PROCESS [J].

KINGMAN, JFC .

ANNALS OF PROBABILITY, 1975, 3 (05) :790-801

← 1 2 →