David Eppstein - Publications

Nordic Journal on Computing (formerly BIT)

• Finding the k smallest spanning trees.
  D. Eppstein.
  2nd Scand. Worksh. Algorithm Theory, Bergen, Norway, 1990.
  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.

  (BibTeX -- Citations -- ACM DL (SWAT) -- ACM DL (BIT))

• Using sparsification for parametric minimum spanning tree problems.
  D. Fernández-Baca, G. Slutzki, and D. Eppstein.
  5th Scand. Worksh. Algorithm Theory, Reykjavik, 1996.
  Lecture Notes in Comp. Sci. 1097, 1996, pp. 149-160, © Springer-Verlag.
  Nordic J. Computing 3(4):352-366, 1996 (special issue for 5th SWAT).

  Given a graph with edge weights that are linear functions of a parameter, finds the sequence of minimum spanning trees produced as the parameter varies, in total time O(mn log n), by combining ideas from "Sparsification" and "Geometric lower bounds". Also solves various problems of optimizing the parameter value, including one closely related to that in "Choosing subsets with maximum weighted average".

  (BibTeX -- Citations -- MIT hypertext bibliography -- ACM DL (SWAT) -- ACM DL (NJC))

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

Semi-automatically filtered from a common source file.