SEQUENCE COMPARISON WITH MIXED CONVEX AND CONCAVE COSTS

被引：46

作者：

EPPSTEIN, D ^{[1
]}

机构：

[1] CSL XEROX PARC,PALO ALTO,CA 94304

来源：

JOURNAL OF ALGORITHMS | 1990年 / 11卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0196-6774(90)90031-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

Recently a number of algorithms have been developed for solving the minimum-weight edit sequence problem with non-linear costs for multiple insertions and deletions. We extend these algorithms to cost functions that are neither convex nor concave, but a mixture of both. We also apply this technique to related dynamic programming algorithms. © 1990.

引用

页码：85 / 101

页数：17

共 15 条

[1]

Aggarwal A., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P497, DOI 10.1109/SFCS.1988.21966

[2]

AGGARWAL A, 1987, ALGORITHMICA, V2, P209

[3]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[4]

Eppstein D., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P488, DOI 10.1109/SFCS.1988.21965