P49: Enumeration of the Euclidean $k$ best spanning trees in a plane with $n$ points
P49: 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(k^2 n + n \log n)$ 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.