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

P59: 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(m \log \log* n + k \min(n, k)^{1/2})$ total time, or a randomized version taking $O(m + k \min(n, k)^{1/2})$ total time.

Comment:

Reference:

[Eppstein1997] (Bibtex)