Publications with Jeff Westbrook
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.