The Least Weight Subsequence Problem

DOI10.1137/0216043MaRDI QIDQ3796786zbMATH OpenOpenAlexFDO

Authors Lawrence L. Larmore, Daniel S. Hirschberg

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://escholarship.org/uc/item/3b6710dc

zbMATH Keywords

directed graphsleast weight subsequenceminimum path

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 concave least-weight subsequence problem revisited
• Finding least-weight subsequences with fewer processors
• Polynomial-time approximation algorithms for weighted LCS problem
• scientific article; zbMATH DE number 7204473
• Alphabetic Minimax Trees

Cited in

(15)

• Sequence comparison with concave weighting functions
• Speeding up dynamic programming with applications to molecular biology
• Dynamic programming with convexity, concavity and sparsity
• 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
• List partitions
• Finding least-weight subsequences with fewer processors
• The concave least-weight subsequence problem revisited
• Categories, relations and dynamic programming
• Weighted Minimum-Length Rearrangement Scenarios.
• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• Tensor ranks and the fine-grained complexity of dynamic programming
• A linear-time algorithm for concave one-dimensional dynamic programming

This page was built for publication: The Least Weight Subsequence Problem

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