Computing the Partition Function for Cliques in a Graph
Computing the Partition Function for Cliques in a Graph
复制标题
计算图中团的配分函数
DOI：
10.4086/toc.2015.v011a013
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Barvinok
中科院分区：
文献类型：
--
作者：
A. Barvinok
我们提出了一种确定性算法，给定一个有 n 个顶点和整数 1 0 的图 G 是绝对常数：我们可以选择 gamma=0.06，如果 n > 4m 且 m > 10，我们可以选择 gamma=0.18。这使我们能够区分不具有 m 个高密度子集的图和具有足够多 m 个高密度子集的图，即使随机命中这样一个子集的概率在 m 中呈指数级小。
We present a deterministic algorithm which, given a graph G with n vertices and an integer 1 0 is an absolute constant: we can choose gamma=0.06, and if n > 4m and m > 10, we can choose gamma=0.18. This allows us to tell apart the graphs that do not have m-subsets of high density from the graphs that have sufficiently many m-subsets of high density, even when the probability to hit such a subset at random is exponentially small in m.