P182: Enumeration of all triangles in a graph

P182: Enumeration of all triangles in a graph

Input:

A graph $G = (V, E)$.

Output:

All triangles in $G$.

Complexity:

$O(\alpha(G)|E|)$ total time and linear space.

Comment:

$\alpha(G)$ is the minimum number of edge-disjoint spanning forests into which $G$ can be decomposed. If $G$ is planar, then the time complexity becomes $O(|V|)$.

Reference:

[Chiba1985] (Bibtex)