Finding Hamilton cycles in random graphs with few queries
Finding Hamilton cycles in random graphs with few queries
复制标题
用很少的查询在随机图中查找汉密尔顿循环
DOI：
10.1002/rsa.20679
复制
发表时间：
2015
影响因子：
1
通讯作者：
Pedro Vieira
中科院分区：
文献类型：
--
作者：
Asaf Ferber;Michael Krivelevich;B. Sudakov;Pedro Vieira
我们在随机图中引入了一组新的算法问题，研究了为了通常找到具有给定目标属性的子图而需要询问 G(n,p) 顶点对之间的邻接性的最小查询数量。我们证明，如果 p≥lnn+lnlnn+ω(1)n ，则在暴露 (1+o(1))n 条边后可以高概率找到哈密顿循环。我们的结果在 p 和暴露边缘的数量上都很严格。 © 2016 Wiley periodicals, Inc. 随机结构。阿尔格., 49, 635–668, 2016
We introduce a new setting of algorithmic problems in random graphs, studying the minimum number of queries one needs to ask about the adjacency between pairs of vertices of G(n,p) in order to typically find a subgraph possessing a given target property. We show that if p≥lnn+lnlnn+ω(1)n , then one can find a Hamilton cycle with high probability after exposing (1+o(1))n edges. Our result is tight in both p and the number of exposed edges. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 635–668, 2016