CHANGES OF LEADERSHIP IN A RANDOM GRAPH PROCESS

被引：5

作者：

ERDOS, P ^{[1
]}

LUCZAK, T ^{[1
]}

机构：

[1] ADAM MICKIEWICZ UNIV POZNAN,DEPT DISCRETE MATH,PL-61712 POZNAN,POLAND

来源：

RANDOM STRUCTURES & ALGORITHMS | 1994年 / 5卷 / 01期

关键词：

D O I：

10.1002/rsa.3240050122

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Let {G(n, M)}M=0(n/2) be a random graph process in which in each step we add to a graph a new edge, chosen at random from all available pairs. Define the leader of G(n, M) as either the unique largest component or, if G(n, M) contains many components of the maximum size, the one from the largest components which emerged first during the process. We show that the longest period between two changes of leaders in the random graph process is, with probability tending to 1 as n --> infinity, of the order of n log log n/log n. (C) 1994 John Wiley & Sons, Inc.

引用

页码：243 / 252

页数：10