Sequence comparison with mixed convex and concave costs

DOI10.1016/0196-6774(90)90031-9zbMath0709.68015OpenAlexW2082378428MaRDI QIDQ3493226

David Eppstein

Publication date: 1990

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(90)90031-9

zbMATH Keywords

cost functionedit distanceconvex costconcave cost

Mathematics Subject Classification ID

Searching and sorting (68P10) Dynamic programming (90C39)

Related Items (18)

Finding least-weight subsequences with fewer processors ⋮ Selection and sorting in totally monotone arrays ⋮ Approximate regular expression pattern matching with concave gap penalties ⋮ Efficient algorithms for some path partitioning problems ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ Structured \(p\)-facility location problems on the line solvable in polynomial time ⋮ Perspectives of Monge properties in optimization ⋮ Consecutive interval query and dynamic programming on intervals ⋮ A linear-time algorithm for concave one-dimensional dynamic programming ⋮ Minimum \(L_k\) path partitioning-an illustration of the Monge property ⋮ A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood ⋮ A Lagrangian relaxation approach for the multiple sequence alignment problem ⋮ Sparse LCS common substring alignment ⋮ Monge strikes again: Optimal placement of web proxies in the internet ⋮ A branch-and-cut algorithm for multiple sequence alignment ⋮ A faster off-line algorithm for the TCP acknowledgement problem.

This page was built for publication: Sequence comparison with mixed convex and concave costs