P60: Enumeration of the Euclidean $k$ best spanning trees in a plane with $n$ points
P60: Enumeration of the Euclidean $k$ best spanning trees in a plane with $n$ points
Input:
$n$ points in a plane
Output:
The Euclidean $k$ best spanning trees of the given points.
Complexity:
$O(n \log n \log k + k \min(k, n)^{1/2})$ total time
Comment:
An Euclidean spanning tree in a plane is a spanning tree of the complete graph whose vertices are all given points and the weight of an edge equal to the Euclidean distance between the corresponding vertices.