Dynamic programming with convexity, concavity and sparsity
From MaRDI portal
Publication:1190452
DOI10.1016/0304-3975(92)90135-3zbMath0763.90088OpenAlexW2014497078MaRDI QIDQ1190452
Publication date: 26 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90135-3
Dynamic programming (90C39) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Fast algorithms for finding disjoint subsequences with extremal densities ⋮ Linear-space algorithms that build local alignments from fragments ⋮ Minimum \(L_k\) path partitioning-an illustration of the Monge property ⋮ Speeding up dynamic programming in the line-constrained \(k\)-median ⋮ Deterministic Algorithms for Unique Sink Orientations of Grids ⋮ Revisiting “Computation of Matrix Chain Products ⋮ The complexity of optimization on grids ⋮ Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots ⋮ Heuristic allocation based on a dynamic programming state-space representation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for concave one-dimensional dynamic programming
- Applications of generalized matrix searching to geometric algorithms
- An optimal algorithm with unknown time complexity for convex matrix searching
- Rapid dynamic programming algorithms for RNA secondary structure
- The longest common subsequence problem revisited
- Geometric applications of a matrix-searching algorithm
- Sequence comparison with concave weighting functions
- Speeding up dynamic programming with applications to molecular biology
- General context-free recognition in less than cubic time
- Preserving order in a forest in less than logarithmic time and linear space
- RNA secondary structure: a complete mathematical analysis
- On the computational power of pushdown automata
- Optimum binary search trees
- On an efficient dynamic programming technique of F. F. Yao
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- Computation of Matrix Chain Products. Part II
- The Context Dependent Comparison of Biological Sequences
- Sequence comparison with mixed convex and concave costs
- A priority queue in which initialization and queue operations takeO(loglogD) time
- A Comprehensive Model of Dynamic Programming
- Algorithms for approximate string matching
- The Least Weight Subsequence Problem
- The concave least-weight subsequence problem revisited
- Computation of Matrix Chain Products. Part I
- Speed-Up in Dynamic Programming
- A linear space algorithm for computing maximal common subsequences
- Bounds for the String Editing Problem
- Bounds on the Complexity of the Longest Common Subsequence Problem
- A fast algorithm for computing longest common subsequences
- Algorithms for the Longest Common Subsequence Problem
- Sparse dynamic programming I
- The String-to-String Correction Problem
- Finite-State Processes and Dynamic Programming
