# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Faster Algorithms for Computing Longest Common Increasing Subsequences

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Brodal, G. S., Kaligosi, K., Katriel, I., & Kutz, M. (2006). Faster Algorithms
for Computing Longest Common Increasing Subsequences. In *Combinatorial Pattern Matching, 17th Annual
Symposium, CPM 2006* (pp. 330-341). Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-22CB-5

##### 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\ge n$, we present an algorithm with an
output-dependent expected running time of $O((m+n\ell) \log\log
\sigma + \cleanSort)$ and $O(m)$ space, where $\ell$ is the length
of an LCIS, $\sigma$ is the size of the alphabet, and $\cleanSort$ is
the time to sort each input sequence.
For $k\ge 3$ length-$n$ sequences we present an algorithm 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.