David Eppstein - Publications

Scandinavian Worksh. Algorithm Theory (SWAT)

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

• The weighted maximum-mean subtree and other bicriterion subtree problems.
  J. Carlson and D. Eppstein.
  arXiv:cs.CG/0503023.
  Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006).
  Lecture Notes in Comp. Sci. 4059, 2006, pp. 397-408.

  We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".

  (BibTeX)

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

Semi-automatically filtered from a common source file.