## G. Cormode and H. Jowhari.
A second look at counting triangles in graph streams (revised).
*Theoretical Computer Science*, 683:22-30, 2017.

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}sqrt(*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, Ostrovsky and Vilenchik, ICALP 2013, which
distinguishes between triangle-free graphs and graphs with at least *T* triangle 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.

[ bib |
http |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*