The paper gives improved solutions for the problem of generating the k smallest spanning trees in a graph and in the plane. The present algorithm for general graphs takes time O(mlogβ(m,n)+k2); for planar graphs this bound can be improved to O(n+k2). The paper also shows that the k best spanning trees for a set of points in the plane can be computed in time O(min(k2n+nlogn, k2+knlog(n/k))). The k best orthogonal spanning trees in the plane can be found in time O(nlogn+knloglog(n/k)+k2).
