Dynamic programming with convexity, concavity and sparsity
type: Item
instance of: scholarly article
title: Dynamic programming with convexity, concavity and sparsity
zbMATH Open document ID: 0763.90088
DOI: 10.1016/0304-3975(92)90135-3
author: Zvi Galil
author: Kunsoo Park
published in: Theoretical Computer Science
publication date: 1992-09-26T00:00:00Z
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90-08
Mathematics Subject Classification ID: 90-02
zbMATH DE Number: 55518
zbMATH Keywords: survey
MaRDI profile type: Publication
full work available at URL: 0304-3975(92)90135-3
OpenAlex ID: W2014497078
cites work: Applications of generalized matrix searching to geometric algorithms
cites work: Geometric applications of a matrix-searching algorithm
cites work: On the computational power of pushdown automata
cites work: Bounds on the Complexity of the Longest Common Subsequence Problem
cites work: Q4065051
cites work: The longest common subsequence problem revisited
cites work: Q3241581
cites work: Dynamic Programming Treatment of the Travelling Salesman Problem
cites work: Q3919065
cites work: Sequence comparison with mixed convex and concave costs
cites work: Sparse dynamic programming I
cites work: Speeding up dynamic programming with applications to molecular biology
cites work: Q4733401
cites work: A linear-time algorithm for concave one-dimensional dynamic programming
cites work: Q4144216
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: A Comprehensive Model of Dynamic Programming
cites work: A linear space algorithm for computing maximal common subsequences
cites work: Algorithms for the Longest Common Subsequence Problem
cites work: The Least Weight Subsequence Problem
cites work: Q5557602
cites work: Q5592246
cites work: Computation of Matrix Chain Products. Part I
cites work: Computation of Matrix Chain Products. Part II
cites work: A fast algorithm for computing longest common subsequences
cites work: A priority queue in which initialization and queue operations takeO(loglogD) time
cites work: Finite-State Processes and Dynamic Programming
cites work: Optimum binary search trees
cites work: An optimal algorithm with unknown time complexity for convex matrix searching
cites work: Q3138930
cites work: Q4130999
cites work: Sequence comparison with concave weighting functions
cites work: Q3707420
cites work: Algorithms for approximate string matching
cites work: General context-free recognition in less than cubic time
cites work: Preserving order in a forest in less than logarithmic time and linear space
cites work: On an efficient dynamic programming technique of F. F. Yao
cites work: The String-to-String Correction Problem
cites work: RNA secondary structure: a complete mathematical analysis
cites work: Rapid dynamic programming algorithms for RNA secondary structure
cites work: The concave least-weight subsequence problem revisited
cites work: The Context Dependent Comparison of Biological Sequences
cites work: Bounds for the String Editing Problem
cites work: Speed-Up in Dynamic Programming
Recommended article: Sparse dynamic programming II
Recommended article: Q6178244
Recommended article: Dynamic programming with value convexity
Recommended article: Stochastic convexity in dynamic programming
Recommended article: Dynamic programming and the Lagrange multipliers
Recommended article: Q3138931
Recommended article: Concave programming for finding sparse solutions to problems with convex constraints
Recommended article: A convex optimization approach to dynamic programming in continuous state and action spaces
Recommended article: A polyhedral approximation approach to concave numerical dynamic programming
Recommended article: DYNAMIC PROGRAMMING, SUCCESSIVE APPROXIMATIONS, AND MONOTONE CONVERGENCE
description: scientific article; zbMATH DE number 55518