Faster Algorithms for Computing Longest Common Increasing Subsequences

Authors

  • Gerth Stølting Brodal
  • Kanela Kaligosi
  • Irit Katriel
  • Martin Kutz

DOI:

https://doi.org/10.7146/brics.v12i37.21904

Abstract

We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths m and n , where m >= n, we present an algorithm with an output-dependent expected running time of O((m + n l) log log sigma + Sort) and O(m) space, where l is the length of an LCIS, sigma is the size of the alphabet, and 'Sort' is the time to sort each input sequence.

For k >= 3 length-n sequences we present an algorithm running time O(min{k r^2, r log^{k-1} r} + Sort), which improves the previous best bound by more than a factor k for many inputs. In both cases, our algorithms are conceptually quite simple but rely on existing sophisticated data structures.

Finally, we introduce the problem of longest common weakly-increasing (or non-decreasing) subsequences (LCWIS), for which we present an O(m + n log n) time algorithm for the 3-letter alphabet case. For the extensively studied Longest Common Subsequence problem, comparable speedups have not been achieved for small alphabets.

Downloads

Published

2005-12-11

How to Cite

Brodal, G. S., Kaligosi, K., Katriel, I., & Kutz, M. (2005). Faster Algorithms for Computing Longest Common Increasing Subsequences. BRICS Report Series, 12(37). https://doi.org/10.7146/brics.v12i37.21904