(min, + ) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences
We study the time complexity of computing the (min, + ) matrix product of two n× n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m1 monotone subsequences and each column of the second matrix can