P83: Enumeration of all spanning trees in a graph

P83: Enumeration of all spanning trees in a graph

Input:

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

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + \tau|V|)$ time and $O(|V| + |E|)$ space (depth first manner) or $O(\tau|V| + |E|)$ space (breadth first manner).

Comment:

By using breadth first manner, the proposed algorithm can be used in a parallel computer.

Reference:

[Matsui1997] (Bibtex)