The Least Weight Subsequence Problem

DOI10.1137/0216043zbMath0651.68092OpenAlexW2152978478MaRDI QIDQ3796786

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 graphsminimum pathleast weight subsequence

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 (11)

List partitions ⋮ Finding least-weight subsequences with fewer processors ⋮ Approximate regular expression pattern matching with concave gap penalties ⋮ Sequence comparison with concave weighting functions ⋮ Categories, relations and dynamic programming ⋮ Speeding up dynamic programming with applications to molecular biology ⋮ Perspectives of Monge properties in optimization ⋮ A linear-time algorithm for concave one-dimensional dynamic programming ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ The algebraic Monge property and path problems ⋮ Distribution-aware compressed full-text indexes

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