P67: Enumeration of all spanning trees in an undirected graph

P67: Enumeration of all spanning trees in an undirected graph

Input:

An undirected graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + |V|N)$ total time and $O(|V| + |E|)$ space.

Comment:

$N$ is the number of spanning trees in $G$.

Reference:

[Gabow1978] (Bibtex)