The Total Acquisition Number Of The Randomly Weighted Path
The Total Acquisition Number Of The Randomly Weighted Path
复制标题
随机加权路径的总采集数
DOI：
--
复制
发表时间：
2015
影响因子：
0.7
通讯作者：
Yiguang Zhang
中科院分区：
文献类型：
--
作者：
A. Godbole;Elizabeth Kelley;Emily Kurtz;P. Prałat;Yiguang Zhang
摘要在确定（g）的（g）的采集号上的大量工作，当这些图的顶点最初分配一个单位权重时在此初始加权方案上的两部分，循环和车轮图，我们的大部分工作都集中在预期的获取数量上，尤其是随机加权图。当N-PATH随机分布在0.242N和0.375N之间的N-PATH时，我们通过计算机支持将其随机分布。和0.29576N。紧密集中于其预期值，在不同的情况下，我们为随机加权路径提供了一种非最佳的采集协议算法，并准确地计算了所得残差集的预期大小。
Abstract There exists a significant body of work on determining the acquisition number at(G) of various graphs when the vertices of those graphs are each initially assigned a unit weight. We determine properties of the acquisition number of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the expected acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number E(at(Pn)) of the n-path when n distinguishable “units” of integral weight, or chips, are randomly distributed across its vertices between 0.242n and 0.375n. With computer support, we improve it by showing that E(at(Pn)) lies between 0.29523n and 0.29576n. We then use subadditivity to show that the limiting ratio lim E(at(Pn))/n exists, and simulations reveal more exactly what the limiting value equals. The Hoeffding-Azuma inequality is used to prove that the acquisition number is tightly concentrated around its expected value. Additionally, in a different context, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and exactly compute the expected size of the resultant residual set.