A second look at counting triangles in graph streams
A second look at counting triangles in graph streams
复制标题
再看一下图形流中的三角形计数
DOI：
10.1016/j.tcs.2014.07.025
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
H. Jowhari
中科院分区：
文献类型：
--
作者：
Graham Cormode;H. Jowhari
在本文中，我们提出了改进的结果在边流图的三角形计数问题。对于具有m条边和至少T个三角形的图，我们证明了在流上额外查看会产生一个两遍流算法，该算法使用O（m <$4.5 T）空间并输出图中三角形数量的（1+ 1）近似值。这改进了Braverman等人的双通流测试仪。[2]该方法在O（mT 1/3）空间内区分了无三角形图和至少有T个三角形的图.此外，在T的依赖性方面，我们表明，更多的通行证不会导致更好的空间约束。换句话说，我们证明了不存在常数通过流算法，该算法使用O（mT 1/2+ ρ）空间区分无三角形图和至少具有T个三角形的图，其中任何常数ρ≥ 0。
In this paper we present improved results on the problem of counting triangles in edge streamed graphs. For graphs with m edges and at least T triangles, we show that an extra look over the stream yields a two-pass streaming algorithm that uses O (m ϵ 4.5 T) space and outputs a (1+ ϵ) approximation of the number of triangles in the graph. This improves upon the two-pass streaming tester of Braverman et al.[2], which distinguishes between triangle-free graphs and graphs with at least T triangles using O (m T 1/3) space. Also, in terms of dependence on T, we show that more passes would not lead to a better space bound. In other words, we prove there is no constant pass streaming algorithm that distinguishes between triangle-free graphs from graphs with at least T triangles using O (m T 1/2+ ρ) space for any constant ρ≥ 0.