A Second Look at Counting Triangles in Graph Streams (revised)

Graham Cormode, Hossein Jowhari

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…