SPARSE DYNAMIC-PROGRAMMING .1. LINEAR COST-FUNCTIONS
SPARSE DYNAMIC-PROGRAMMING .1. LINEAR COST-FUNCTIONS
复制标题
DOI：
10.1145/146637.146650
复制
发表时间：
1992-07-01
影响因子：
2.5
通讯作者：
ITALIANO, GF
中科院分区：
文献类型：
--
作者：
EPPSTEIN, D;GALIL, Z;ITALIANO, GF
考虑了用于序列比较和RNA二级结构预测的许多不同递归方程的动态规划解。这些递归是在多个点上定义的，这些点在输入大小上是二次的；然而，只有稀疏集才会影响结果。当递推过程中使用的权函数为线性时，给出了这些问题的有效算法。算法的时间复杂性几乎线性地依赖于需要考虑的点的数量；当问题稀疏时，这导致与已知算法相比有很大的加速。
Dynamic programming solutions to a number of different recurrence equations for sequence comparison and for RNA secondary structure prediction are considered. 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. Efficient algorithms for these problems are given, when the weight functions used in the recurrences are taken to be linear. The time complexity of the algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse this results in a substantial speed-up over known algorithms.