David Eppstein - Publications
Journal of the Association for Computing Machinery
Hypertext Bibliography Project at MIT
listings of my J. ACM papers.
- Sparsification--A technique for speeding up dynamic graph algorithms.
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.
MIT hypertext bibliography --
David Eppstein --
Theory Group --
Inf. & Comp. Sci. --
from a common source file.