A LINEAR-TIME ALGORITHM FOR CONCAVE ONE-DIMENSIONAL DYNAMIC-PROGRAMMING

被引：42

作者：

GALIL, Z ^{[1
]}

PARK, K ^{[1
]}

机构：

[1] TEL AVIV UNIV,DEPT COMP SCI,IL-69978 TEL AVIV,ISRAEL

来源：

关键词：

Dynamic programming; quadrangle inequality; total monotonicity;

D O I：

10.1016/0020-0190(90)90215-J

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

[No abstract available]

引用

页码：309 / 311

页数：3

共 7 条

[1] GEOMETRIC APPLICATIONS OF A MATRIX-SEARCHING ALGORITHM [J].

AGGARWAL, A ;

KLAWE, MM ;

MORAN, S ;

SHOR, P ;

WILBER, R .

[2]

EPPSTEIN D, IN PRESS J ALGORITHM

GALIL, Z ;

GIANCARLO, R .

[4] THE LEAST WEIGHT SUBSEQUENCE PROBLEM [J].

HIRSCHBERG, DS ;

LARMORE, LL .

[5]

LARMORE LL, IN PRESS 1ST ANN ACM

[6] THE CONCAVE LEAST-WEIGHT SUBSEQUENCE PROBLEM REVISITED [J].

WILBER, R .

[7] SPEED-UP IN DYNAMIC-PROGRAMMING [J].

YAO, FF .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (04) :532-540