**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.

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.