License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.4
URN: urn:nbn:de:0030-drops-133487
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13348/
Go to the corresponding LIPIcs Volume Portal

Agrawal, Anadi ; Gawrychowski, Paweł

A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem

pdf-format:
LIPIcs-ISAAC-2020-4.pdf (0.4 MB)

Abstract

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).

BibTeX - Entry

@InProceedings{agrawal_et_al:LIPIcs:2020:13348,
  author =	{Anadi Agrawal and Pawe{\l} Gawrychowski},
  title =	{{A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13348},
  URN =		{urn:nbn:de:0030-drops-133487},
  doi =		{10.4230/LIPIcs.ISAAC.2020.4},
  annote =	{Keywords: Longest Common Increasing Subsequence, Four Russians}
}

Keywords: Longest Common Increasing Subsequence, Four Russians
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI