David Eppstein - Publications

Journal of the Association for Computing Machinery

• Sparsification--A technique for speeding up dynamic graph algorithms.
  D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig.
  33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 60-69.
  Tech. Rep. RC 19272 (83907), IBM, 1993.
  Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
  J. ACM 44(5):669-696, 1997.

  Uses a divide and conquer on the edge set of a graph, together with the idea of replacing subgraphs by sparser certificates, to make various dynamic algorithms as fast on dense graphs as they are on sparse graphs. Applications include random generation of spanning trees as well as finding the k minimum weight spanning trees for a given parameter k.

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

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

Semi-automatically filtered from a common source file.