Home

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

Zvi Galil; Kunsoo Park

Title:
A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming
Author(s):
Galil, Zvi
Park, Kunsoo
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
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:
143
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use