The Input/Output Complexity of Triangle Enumeration

Rasmus Pagh, Francesco Silvestri

We consider the well-known problem of enumerating all triangles of an undirected graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let $E$ be the number of edges, $M 0$. Our results are based on a new color coding technique, which may be of independent interest.

Knowledge Graph



Sign up or login to leave a comment