David Eppstein - Publications

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