# David Eppstein - Publications

##

**Maintenance of a minimum spanning forest in a dynamic plane graph**.

D. Eppstein,
G.F. Italiano,
R. Tamassia,
R.E. Tarjan,
J. Westbrook,
and M. Yung.

*1st ACM-SIAM Symp. Discrete Algorithms,*
San Francisco, 1990, pp. 1–11.

*J. Algorithms* 13 (1): 33–54, 1992
(special issue for 1st Symp. Discrete Algorithms).

Corrigendum, *J. Algorithms* 15: 173, 1993.
The complement of a
minimum spanning tree is a maximum spanning tree in
the dual graph. By applying this fact we can use a modified form of
Sleator and Tarjan's dynamic tree data structure to update the MST in
logarithmic time per update.

(BibTeX –
Citations –
CiteSeer –
ACM DL)

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

Semi-automatically filtered
from a common source file.