Finding cliques using few probes
Finding cliques using few probes
复制标题
使用少量探针发现派系
DOI：
10.1002/rsa.20896
复制
发表时间：
2019
影响因子：
1
通讯作者：
Tetali, Prasad
中科院分区：
文献类型：
--
作者：
Feige, Uriel;Gamarnik, David;Neeman, Joe;Rácz, Miklós Z.;Tetali, Prasad
考虑一种计算时间无界的算法，该算法探测邻接矩阵的结点，需要输出一个团。我们表明，如果输入图是随机绘制的（因此可能有一个大小大致的团），那么对于每个δ<2和常数r，存在一个α<2（可能依赖于δ和r），使得在r轮中进行nδ探测的算法不可能（在随机图的选择上）输出一个大小大于的团。
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of annvertex graph, and need to output a clique. We show that if the input graph is drawn at random from (and hence is likely to have a clique of size roughly ), then for everyδ<2 and constantℓ, there is anα<2 (that may depend onδandℓ) such that no algorithm that makesnδprobes inℓrounds is likely (over the choice of the random graph) to output a clique of size larger than .
用很少的查询在随机图中查找汉密尔顿循环
影响因子：
1
作者：
Asaf Ferber;Michael Krivelevich;B. Sudakov;Pedro Vieira
通讯作者：
Pedro Vieira
在稀疏随机图中查找路径需要许多查询
影响因子：
1
作者：
Asaf Ferber;Michael Krivelevich;B. Sudakov;Pedro Vieira
通讯作者：
Pedro Vieira
在线拉姆齐数和子图查询问题
DOI：
--
发表时间：
2018
期刊：
Bolyai Society Mathematical Studies
影响因子：
--
作者：
D. Conlon;J. Fox;A. Grinshpun;Xiaoyu He
通讯作者：
Xiaoyu He