P285: Enumeration of all spanning trees of an weighted graph in order of increasing cost

P285: Enumeration of all spanning trees of an weighted graph in order of increasing cost

Input:

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

Output:

All spanning trees of $G$ in order of increasing cost.

Complexity:

$O(N|E|\log |E| + N^2)$ total time and $O(N|E|)$ space.

Comment:

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

Reference:

[Sorensen2005] (Bibtex)