Graph / Triangle (Bibtex)

P395: Enumeration of all minimal triangle graphs with a fixed number vertices

Input:

An integer $n$.

Output:

All minimal triangle graphs with $n$ vertices.

Complexity:

Comment:

Reference:

[Bowen1967b] (Bibtex)

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)

P493: Enumeration of all triangles in a graph.

Input:

A graph $G$.

Output:

All triangles in $G$.

Complexity:

$O(m^{3/2})$ total time.

Comment:

Reference:

[Schank2005] (Bibtex)