Sequence comparison with mixed convex and concave costs

David Eppstein
J. Algorithms 11(1):85–101, Mar 1990
Tech. report CUCS-382-88, Columbia Univ., Computer Science Dept., 1988
Mathematical Reviews 91h:68031

Cited by:

• Improved algorithms for economic lot size problems
• Selection in monotone matrices and computing $k$th nearest neighbors
• Image analysis and computer vision: 1990
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Dynamic programming with convexity, concavity and sparsity
• Selection and sorting in totally monotone arrays
• Improved selection in totally monotone arrays
• Linear and $O(n\log n)$ time minimum-cost matching algorithms for quasi-convex tours
• A linear time algorithm for concave one-dimensional dynamic programming
• Finding least-weight subsequences with fewer processors
• Parallel algorithms for dynamic programming recurrences with more than $O(1)$ dependency
• Superlinear bounds for matrix searching problems
• A special case of the $n$-vertex traveling-salesman problem that can be solved in $O(n)$ time
• Dynamic programming: special cases
• Approximate regular expression pattern matching with concave gap penalties
• Efficient algorithms for some path partitioning problems
• Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood
• Perspectives of Monge properties in optimization
• Fast solution and detection of minimal forecast horizons in dynamic programs with a single indicator of the future – applications to dynamic lot-sizing models
• Parallel dynamic programming
• Discrete Pattern Matching over Sequences and Interval Sets
• Shortest path in complete bipartite digraph problem and its applications
• Efficiently solvable special cases of hard combinatorial optimization problems
• Structured $p$-facility location problems on the line solvable in polynomial time
• Well-solvable special cases of the traveling salesman problem: A survey
• Process Discovery and Validation through Event-Data Analysis
• Software process validation: quantitatively measuring the correspondence of a process to a model using event-based data
• An algorithm for shortest paths in bipartite digraphs with concave weight matrices and its applications
• Monge strikes again: optimal placement of web proxies in the Internet
• Approximation of staircases by staircases
• A sub-quadratic sequence alignment algorithm for unrestricted cost matrices
• A faster off-line algorithm for the TCP acknowledgement problem
• Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics
• Sparse LCS common substring alignment
• Note on approximate comparison of sequences with normalization