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

P51: 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|\alpha (|E|,|V|) + |E|\log |E|)$ total time and $O(k + |E|)$ space, $\alpha(\cdot)$ is Tarjan's inverse of Ackermann's function.

Comment:

Reference:

[Gabow1977] (Bibtex)