P192: Enumeration of all $P_3$'s in a graph

P192: Enumeration of all $P_3$'s in a graph

Input:

A graph $G$.

Output:

All of all $P_3$'s in $G$.

Complexity:

$O(|E|^{1.5} + p_3(G))$ total time.

Comment:

$P_3$ is a induced path of $G$ with three vertices and $p_3(G)$ is the number of $P_3$ in $G$.

Reference:

[Hoang2013] (Bibtex)