P447: Enumeration of all spanning trees in an undirected and weighted graph in increasing order.

P447: Enumeration of all spanning trees in an undirected and weighted graph in increasing order.

Input:

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

Output:

All spanning trees in $G$ in increasing order.

Complexity:

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

Comment:

Polynomial amortized time.

Reference:

[Kapoor1995] (Bibtex)