Suman K. Bera

How the Degeneracy Helps for Triangle Counting in Graph Streams

2020 · arXiv (Cornell University)

We revisit the well-studied problem of triangle count estimation in graph streams. Given a graph represented as a stream of $m$ edges, our aim is to compute a $(1\pm\varepsilon)$-approximation to the triangle count $T$, using …