David Eppstein – Publications

Publications with David Fernández-Baca

• Using sparsification for parametric minimum spanning tree problems.
  D. Fernández-Baca, G. Slutzki, and D. Eppstein.
  5th Scand. Worksh. Algorithm Theory, Reykjavik, 1996.
  Springer, Lecture Notes in Comp. Sci. 1097, 1996, pp. 149–160.
  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".