P445: Enumeration of all spanning trees in a graph

P445: Enumeration of all spanning trees in a graph

Input:

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

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + N|V|)$ total time with $O(|V|^2)$ space, where $N$ is the number of solutions.

Comment:

Polynomial amortized time.

Reference:

[Winter1986] (Bibtex)