Andrew McGregor

Better Algorithms for Counting Triangles in Data Streams

2016

We present space-efficient data stream algorithms for approximating the number of triangles in a graph up to a factor 1+ε. While it can be shown that determining whether a graph is triangle-free is not possible …