Finding Adam in random growing trees
Finding Adam in random growing trees
复制标题
在随机生长的树中寻找亚当
DOI：
10.1002/rsa.20649
复制
发表时间：
2014
影响因子：
1
通讯作者：
G. Lugosi
中科院分区：
文献类型：
--
作者：
Sébastien Bubeck;L. Devroye;G. Lugosi
我们研究了在由均匀依附模型和优先依附模型生成的大树中寻找第一顶点的算法。我们要求算法输出K个顶点的集合，使得概率至少为1−ε的第一个顶点在该集合中。我们证明了对于任何ε，都存在K与输入树大小无关的算法。此外，我们还给出了K作为ε的函数的最优值的几乎紧界。在一致依附情形下，我们证明了最优K是1/ε中的次多项式，并且它至少是超多对数的。另一方面，由于我们证明了最佳K在1/ε上是多项式的，所以优先依附情形的难度是指数级的。我们用几个有待解决的问题来结束这篇论文。©2016威利期刊公司随机结构。2017年，50,158-172
We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least 1−ε , the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε. In the uniform attachment case we show that the optimal K is subpolynomial in 1/ε , and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in 1/ε . We conclude the paper with several open problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 158–172, 2017
寻找第一个顶点
DOI：
10.1214/16-aap1212
发表时间：
2017
期刊：
The Annals of Applied Probability
影响因子：
--
作者：
Frieze, Alan;Pegden, Wesley
通讯作者：
Pegden, Wesley