Faster Algorithms for Computing Longest Common Increasing Subsequences

Gerth Stølting Brodal, Kanela Kaligosi, Irit Katriel, and Martin Kutz

Technical Report, BRICS-RS-05-37, BRICS, Department of Computer Science, Aarhus University, 16 pages, December 2005.

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 mn, we present an algorithm with an output-dependent expected running time of O((m+nl) loglog σ + Sort) and O(m) space, where l is the length of a LCIS, σ 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 with running time O(min{kr2,rlogk-1r}+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+nlog 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.

Copyright notice

Copyright © 2005, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-05-37.pdf (205 Kb)

BIBTEX entry

@techreport{brics-rs-05-37,
  author = "Gerth St{\o}lting Brodal and Kanela Kaligosi and Irit Katriel and Martin Kutz",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "December",
  number = "BRICS-RS-05-37",
  pages = "16",
  title = "Faster Algorithms for Computing Longest Common Increasing Subsequences",
  year = "2005"
}