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.

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

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

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

Semi-automatically filtered from a common source file.