2026-07-25T21:15:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13348 2024-03-06T10:51:45Z ddc:004 open_access

A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem Agrawal, Anadi Gawrychowski, Paweł Longest Common Increasing Subsequence Four Russians The Longest Common Increasing Subsequence (LCIS) is a variant of the classical Longest Common Subsequence (LCS), in which we additionally require the common subsequence to be strictly increasing. While the well-known "Four Russians" technique can be used to find LCS in subquadratic time, it does not seem directly applicable to LCIS. Recently, Duraj [STACS 2020] used a completely different method based on the combinatorial properties of LCIS to design an 𝒪(n²(log log n)²/log^{1/6}n) time algorithm. We show that an approach based on exploiting tabulation (more involved than "Four Russians") can be used to construct an asymptotically faster 𝒪(n² log log n/√{log n}) time algorithm. As our solution avoids using the specific combinatorial properties of LCIS, it can be also adapted for the Longest Common Weakly Increasing Subsequence (LCWIS). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anadi Agrawal and Paweł Gawrychowski 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.4 urn:nbn:de:0030-drops-133487 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.4 eng https://creativecommons.org/licenses/by/3.0/legalcode