THE MINIMAL SPANNING TREE IN A COMPLETE GRAPH AND A FUNCTIONAL LIMIT-THEOREM FOR TREES IN A RANDOM GRAPH

被引：46
作者：
JANSON, S
机构：
[1] Department of Mathematics, Uppsala University, Uppsala, S-751 06
来源：
RANDOM STRUCTURES & ALGORITHMS | 1995年 / 7卷 / 04期
关键词：
D O I：
10.1002/rsa.3240070406
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
The minimal weight of a spanning tree in a complete graph K-n with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph. (C) 1995 John Wiley & Sons, Inc.
引用
收藏
页码：337 / 355
页数：19
相关论文
共 11 条
[1]   POISSON CONVERGENCE AND RANDOM GRAPHS [J].
BARBOUR, AD .
MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1982, 92 (SEP) :349-359
[2]  
Billingsley P., 2013, CONVERGE PROBAB MEAS
[3]  
Bollobas B., 1985, RANDOM GRAPHS
[4]  
Cayley Arthur, 1889, Q J PURE APPL MATH, V23, P376, DOI [10.1017/cbo9780511703799.010, DOI 10.1017/CBO9780511703799]
[5]   ON THE VALUE OF A RANDOM MINIMUM SPANNING TREE PROBLEM [J].
FRIEZE, AM .
DISCRETE APPLIED MATHEMATICS, 1985, 10 (01) :47-56
[6]   A LINEAR-TIME ALGORITHM FOR FINDING A MINIMUM SPANNING PSEUDOFOREST [J].
GABOW, HN ;
TARJAN, RE .
INFORMATION PROCESSING LETTERS, 1988, 27 (05) :259-263
[7]   MULTICYCLIC COMPONENTS IN A RANDOM GRAPH PROCESS [J].
JANSON, S .
RANDOM STRUCTURES & ALGORITHMS, 1993, 4 (01) :71-84
[8]  
JANSON S., 1994, MEM AM MATH SOC, V534
[9]  
Kruskal M., 1954, AM MATH MONTHLY, V61, P392
[10]  
Pittel B., 1990, RANDOM STRUCT ALGOR, V1, P311
12