“The Least Weight Subsequence Problem”, 1987-08 (; backlinks):
[superseded by 1988] The least weight subsequence (LWS) problem is introduced, and is shown to be equivalent to the classic minimum path problem for directed graphs. A special case of the LWS problem is shown to be solvable in time 𝒪(n log n) generally and, for certain weight functions, in linear time.
A number of applications are given, including an optimum paragraph formation problem and the problem of finding a minimum height B-tree, whose solutions realize improvement in asymptotic time complexity.
View PDF: