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

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

Input:

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

Output:

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

Complexity:

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

Comment:

Reference:

[Frederickson1985] (Bibtex)