It is named after the initials of its five inventors, Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber, and Maria Klawe.
It is totally monotone if the same property is true for every submatrix (defined by an arbitrary subset of the rows and columns of the given matrix).
Equivalently, a matrix is totally monotone if there does not exist a 2×2 submatrix whose row minima are in the top right and bottom left corners.
The basic idea of the algorithm is to follow a prune and search strategy in which the problem to be solved is reduced to a single recursive subproblem of the same type whose size is smaller by a constant factor.
Subsequent research found applications of the same algorithm in breaking paragraphs into lines,[2] RNA secondary structure prediction,[3] DNA and protein sequence alignment,[4][5] the construction of prefix codes,[6] and image thresholding,[7] among others.