David Eppstein – Publications

Publications with Monika R. Henzinger

Parametric and kinetic minimum spanning trees.
P. K. Agarwal, D. Eppstein, L. J. Guibas, and M. R. Henzinger.
39th IEEE Symp. Foundations of Comp. Sci., 1998, pp. 596–605..

We describe algorithms for maintaining the minimum spanning tree in a graph in which the edge weights are piecewise linear functions of time that may change unpredictably. We solve the problem in time O(n^2/3 polylog n) per combinatorial change to the tree for general graphs, and in time O(n^1/4 polylog n) per combinatorial change to the tree for planar graphs.

(FOCS '98 talk slides)