David Eppstein – Publications

Publications with Moti Yung

• Maintenance of a minimum spanning forest in a dynamic plane graph.
  D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung.
  1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 1–11.
  J. Algorithms 13 (1): 33–54, 1992 (special issue for 1st Symp. Discrete Algorithms).
  Corrigendum, J. Algorithms 15: 173, 1993.

  The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.

• Efficient sequential and parallel algorithms for computing recovery points in trees and paths.
  M. Chrobak, D. Eppstein, G.F. Italiano, and M. Yung.
  2nd ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1991, pp. 158–167.
  ALCOM Report 91-74, University of Rome, 1991.

  Described slightly superlinear algorithms for partitioning a tree into a given number of subtrees, making them all as short as possible. Frederickson at the same conference further improved the sequential time to linear. There may still be something worth publishing in the parallel algorithms.