The concave least-weight subsequence problem revisited

DOI10.1016/0196-6774(88)90032-6zbMath0651.68093OpenAlexW2057640376WikidataQ56520005 ScholiaQ56520005MaRDI QIDQ3796787

Robert Wilber

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0196-6774(88)90032-6

zbMATH Keywords

concave least-weight subsequencetext formatting system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Data structures (68P05) Discrete mathematics in relation to computer science (68R99)

Related Items (28)

A note on the traveling repairman problem ⋮ Finding least-weight subsequences with fewer processors ⋮ Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications ⋮ Online dynamic programming speedups ⋮ Selection and sorting in totally monotone arrays ⋮ Approximate regular expression pattern matching with concave gap penalties ⋮ Speeding up dynamic programming with applications to molecular biology ⋮ Spanning trees and shortest paths in Monge graphs ⋮ 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 ⋮ On three soft rectangle packing problems with guillotine constraints ⋮ Monge properties of sequence alignment ⋮ A linear-time algorithm for concave one-dimensional dynamic programming ⋮ Applications of generalized matrix searching to geometric algorithms ⋮ Minimum \(L_k\) path partitioning-an illustration of the Monge property ⋮ Improved complexity bounds for location problems on the real line ⋮ 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 ⋮ New algorithms for facility location problems on the real line ⋮ Computing an eigenvector of a Monge matrix in max-plus algebra ⋮ The \(k\)-centrum multi-facility location problem ⋮ The algebraic Monge property and path problems ⋮ Distribution-aware compressed full-text indexes ⋮ Unnamed Item ⋮ On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines ⋮ Monge strikes again: Optimal placement of web proxies in the internet ⋮ A faster off-line algorithm for the TCP acknowledgement problem.

This page was built for publication: The concave least-weight subsequence problem revisited