Name
Abstract | ||
|---|---|---|
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.5T) 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(mT1/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(mT1/2+ρ) space for any constant ρ≥0. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2014.07.025 | Theoretical Computer Science |
Keywords | DocType | Volume |
Data streams,Randomized algorithms,Graphs | Journal | 552 |
ISSN | Citations | PageRank |
0304-3975 | 5 | 0.41 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Graham Cormode | 1 | 3869 | 188.38 |
| Hossein Jowhari | 2 | 172 | 8.53 |