- Finding the k smallest spanning trees.
D. Eppstein.
2nd Scand. Worksh. Algorithm Theory, Bergen, Norway, 1990.
Springer, Lecture Notes in Comp. Sci. 447, 1990, pp. 38–47.
BIT 32: 237–248, 1992 (special issue for 2nd Scand. Worksh. Algorithm Theory).By removing edges not involved in some solution, and contracting edges involved in all solutions, we reduce the problem to one in a graph with O(k) edges and vertices. This simplification step transforms any time bound involving m or n to one involving min(m, k) or min(n, k) respectively. This paper also introduces the geometric version of the k smallest spanning trees problem (the graph version was long known) which it solves using order (k+1) Voronoi diagrams.