Reports

A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming

Galil, Zvi; Park, Kunsoo

The least weight subsequence problem is a special case of the one-dimensional dynamic programming problem where D[i] = E[i]. The modified edit distance problem, which arises in molecular biology. geology, and speech recognition, can be decomposed into 2n copies of the problem.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-469-89
Published Here
January 11, 2012