Avoiding a giant component
Avoiding a giant component
复制标题
避免使用巨大的组件
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
A. Frieze
中科院分区：
文献类型：
--
作者：
T. Bohman;A. Frieze
令 e1, e′1; e2, e′2;…;ei, e′i;⋅⋅⋅ 是从完整图 Kn 的边集中均匀随机选择的有序边对序列（即我们进行放回采样）。该序列用于通过在阶段 i, i=1,… 选择 ei,e′i 中的一条边作为图中的一条边来形成图，其中阶段 i 的选择仅基于对阶段 i 出现的边的观察。我们证明，可以做出这些选择，使得在 0.535n 阶段形成的图的最大分量的大小是 n 的多对数。这解决了 Achlioptas 的问题。 © 2001 John Wiley & Sons, Inc. 随机结构。阿尔格., 19, 75–85, 2001
Let e1, e′1; e2, e′2;…;ei, e′i;⋅⋅⋅ be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph Kn (i.e. we sample with replacement). This sequence is used to form a graph by choosing at stage i, i=1,…, one edge from ei,e′i to be an edge in the graph, where the choice at stage i is based only on the observation of the edges that have appeared by stage i. We show that these choices can be made so that whp the size of the largest component of the graph formed at stage 0.535n is polylogarithmic in n. This resolves a question of Achlioptas. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 75–85, 2001