A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
复制标题
计算给定图中子图频率的快速逼近算法
DOI：
10.1137/s0097539793247634
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
V. Rödl
中科院分区：
文献类型：
--
作者：
R. Duke;H. Lefmann;V. Rödl
在本文中，我们给出了一个算法，给定一个标记图的$n$顶点和一个列表的所有标记图的$k$顶点，提供了这个列表中的每个图$H$的诱导副本的数量的近似$H$在$G$与总误差小。这个算法的运行时间是O（n^{{1 \over \log \log n}} \cdot M（n））$，其中$M（n）$是对一个n × n矩阵进行平方所需的时间，其中0，1是整数。设计该算法的主要工具是Szemeredi正则引理的一个变体。
In this paper we give an algorithm which, given a labeled graph on $n$ vertices and a list of all labeled graphs on $k$ vertices, provides for each graph $H$ of this list an approximation to the number of induced copies of $H$ in $G$ with total error small. This algorithm has running time $O(n^{{1 \over \log \log n}} \cdot M(n))$, where $M(n)$ is the time needed to square a $n$ by $n$ matrix with 0, 1-entries over the integers. The main tool in designing this algorithm is a variant of the regularity lemma of Szemeredi.