P53: Enumeration of the $k$ smallest weight spanning trees in a graph in increasing order

P53: Enumeration of the $k$ smallest weight spanning trees in a graph in increasing order

Input:

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

Output:

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

Complexity:

$O(|E|\log\log_{(2+|E|/|V|)} n + k^2\sqrt{|E|})$ total time and $O(|E| + k\sqrt{|E|})$ space.

Comment:

Reference:

[Frederickson1985] (Bibtex)