Home

Sparse Dynamic Programming I: Linear Cost Functions

David Eppstein; Zvi Galil; Raffaele Giancarlo; Giuseppe F. Italiano

Title:
Sparse Dynamic Programming I: Linear Cost Functions
Author(s):
Eppstein, David
Galil, Zvi
Giancarlo, Raffaele
Italiano, Giuseppe F.
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-471-89
Publisher:
Department of Computer Science, Columbia University
Publisher Location:
New York
Abstract:
We consider dynamic programming solutions to a number of different recurrences for sequence comparison and for RNA secondary structure prediction. These recurrences are defined over a number of points that is quadratic in the input size; however only a sparse set matters for the result. We give efficient algorithms for these problems, when the weight functions used in the recurrences are taken to be linear. Our algorithms reduce the best known bounds by a factor almost linear in the density of the problems: when the problems are sparse this results in a substantial speed-up.
Subject(s):
Computer science
Item views:
98
Metadata:
text | xml

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