Technical reports:
A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming
Zvi Galil; Kunsoo Park
Downloads:
- Title:
- A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming
- Author(s):
-
Galil, Zvi
Park, Kunsoo - Date:
- 1989
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:12178
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-469-89
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Abstract:
- 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.
- Subject(s):
- Computer science
- Item views:
- 83