**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)

**Sparse dynamic programming**.

D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.

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

"Sparse dynamic programming I: linear cost functions",*J. ACM*39: 519–545, 1992.

"Sparse dynamic programming II: convex and concave cost functions",*J. ACM*39: 546–567, 1992.Considers sequence alignment and RNA structure problems in which the solution is constructed by piecing together some initial set of fragments (e.g. short sequences that match exactly). The method is to consider a planar point set formed by the fragment positions in the two input sequences, and use plane sweep to construct a cellular decomposition of the plane similar to the rectilinear Voronoi diagram.

(BibTeX – Citations to conference version – Citations to SDP I – Citations to SDP II)

**Efficient algorithms for sequence analysis**.

D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.

*International Advanced Workshop on Sequences,*Positano, Italy, 1991.

*Sequences II: Methods in Communication, Security, and Computer Science,*R.M. Capocelli, A. De Santis, and U. Vaccaro, eds., Springer, 1993, pp. 225–244.

Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.

(BibTeX – Citations – CiteSeer)

**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.

**Sparsification--A technique for speeding up dynamic graph algorithms**.

D. Eppstein, Z. Galil, 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.*(BibTeX – Citations – MIT hypertext bibliography – ACM DL)

**Improved sparsification**.

D. Eppstein, Z. Galil, and G.F. Italiano.

Tech. Rep. 93-20, ICS, UCI, 1993.Saves a log factor over dynamic graph algorithms in "Sparsification" and their applications, by dividing vertices instead of edges. Merged into the journal version of "Sparsification".

(BibTeX – Citations – CiteSeer)

**Separator based sparsification for dynamic planar graph algorithms**.

D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.

*25th ACM Symp. Theory of Computing,*San Diego, 1993, pp. 208–217.Replaces portions of a hierarchical separator decomposition with smaller certificates to achieve fast update times for various dynamic planar graph problems. Applications include finding the

*k*best spanning trees of a planar graph.(BibTeX – Citations – MIT hypertext bibliography)

**Separator based sparsification I: planarity testing and minimum spanning trees**.

D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.

*J. Comp. Sys. Sci.*52: 3–27, 1996 (special issue for 25th STOC).First half of journal version of Separator based sparsification for dynamic planar graph algorithms.

**Separator based sparsification II: edge and vertex connectivity**.

D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.

Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.

*SIAM J. Computing*28 (1): 341–381, 1999.Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.

**Dynamic graph algorithms**.

D. Eppstein, Z. Galil, and G.F. Italiano.

Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.

*Algorithms and Theoretical Computing Handbook,*M. J. Atallah, ed., CRC Press, 1999, chapter 8.

2nd. ed., CRC Press, 2010, Vol. I: General Concepts and Techniques, chapter 9, pp. 9–1 - 9-28.(BibTeX – Citations – CiteSeer)

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

Semi-automatically filtered from a common source file.