David Eppstein - Publications

Publications with Tom Spencer

• Separator based sparsification for dynamic planar graph algorithms.
  D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
  25th ACM Symp. Theory of Computing, San Diego, 1993, pp. 208-217.

  Replaces portions of a hierarchical separator decomposition with smaller certificates to achieve fast update times for various dynamic planar graph problems. Applications include finding the k best spanning trees of a planar graph.

  (BibTeX -- Citations -- MIT hypertext bibliography)

• Separator based sparsification I: planarity testing and minimum spanning trees.
  D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
  J. Comp. Sys. Sci. 52:3-27, 1996 (special issue for 25th STOC).

  First half of journal version of Separator based sparsification for dynamic planar graph algorithms.

  (Citations -- ACM DL)

• Separator based sparsification II: edge and vertex connectivity.
  D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
  Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.
  SIAM J. Computing 28(1):341-381, 1999.

  Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.

  (Citations -- ACM DL)

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

Semi-automatically filtered from a common source file.