# David Eppstein - Publications

##

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

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

Semi-automatically filtered
from a common source file.