David Eppstein - Publications
Publications with Moti Yung
- Maintenance of a minimum spanning forest in a dynamic plane graph.
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.
- Efficient sequential and parallel algorithms for
computing recovery points in trees and paths.
M. Chrobak, D. Eppstein,
G.F. Italiano, and M. Yung.
2nd ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1991, pp. 158–167.
ALCOM Report 91-74, University of Rome, 1991.
Described slightly superlinear algorithms for partitioning a tree into a
given number of subtrees, making them all as short as possible.
Frederickson at the same conference
further improved the sequential time to linear. There may still be
something worth publishing in the parallel algorithms.
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
from a common source file.