The concave least-weight subsequence problem revisited

DOI10.1016/0196-6774(88)90032-6MaRDI QIDQ3796787zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

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

Recommendations

• The Least Weight Subsequence Problem
• Finding least-weight subsequences with fewer processors
• A linear-time algorithm for concave one-dimensional dynamic programming
• Speeding up dynamic programming with applications to molecular biology
• Sequence comparison with concave weighting functions

Cited in

(31)

• Speeding up dynamic programming with applications to molecular biology
• 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
• The smallest upravel
• Finding a minimum-weight k-link path in graphs with the concave Monge property and applications
• Spanning trees and shortest paths in Monge graphs
• Structured \(p\)-facility location problems on the line solvable in polynomial time
• Consecutive interval query and dynamic programming on intervals
• Monge strikes again: Optimal placement of web proxies in the internet
• A faster off-line algorithm for the TCP acknowledgement problem.
• The algebraic Monge property and path problems
• Approximate regular expression pattern matching with concave gap penalties
• Perspectives of Monge properties in optimization
• Distribution-aware compressed full-text indexes
• On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
• Finding least-weight subsequences with fewer processors
• On three soft rectangle packing problems with guillotine constraints
• Computing an eigenvector of a Monge matrix in max-plus algebra
• The Least Weight Subsequence Problem
• Selection and sorting in totally monotone arrays
• Monge properties of sequence alignment
• A note on the traveling repairman problem
• Capacitated dynamic programming: faster knapsack and graph algorithms
• New algorithms for facility location problems on the real line
• The k-centrum multi-facility location problem
• Tensor ranks and the fine-grained complexity of dynamic programming
• Online dynamic programming speedups
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3796787)