1. Home
    Item seperator
  3. Item seperator
    The Concave Least Weight Subsequence Problem Revisited

The Concave Least Weight Subsequence Problem Revisited

New Image

Hirschberg and Larmore [2] showed that the concave least weight subsequence problem can be solved in O(n log n) time and that of a certain extra condition is imposed it can be soled in O(n) time. Here we show that the concave least weight subsequence problem can always be solved in O(n) time, without any extra conditions.