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

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

Semi-automatically filtered from a common source file.