P55: Enumeration of the $k$ smallest weight spanning trees in a graph

P55: Enumeration of the $k$ smallest weight spanning trees in a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ smallest weight spanning trees in $G$.

Complexity:

$O(k|E| + \min (|V|^2 ,|E|\log \log |V|))$ total time and $O(k + |E|)$ space

Comment:

Reference:

[Katoh1981] (Bibtex)