A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem

Lech Duraj
The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated Longest Common Subsequence (LCS) problem. For LCIS, as well as for LCS, there is an 𝒪(n²)-time algorithm and a SETH-based conditional lower bound of 𝒪(n^{2-ε}). For LCS, there is also the Masek-Paterson 𝒪(n²/log n)-time algorithm, which does not seem to adapt to LCIS in any obvious way. Hence, a natural question arises: does any (slightly) sub-quadratic algorithm exist for the Longest...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.