# Faster Algorithms for Computing Longest Common Increasing Subsequences

In * Proc. 17th Annual Symposium on Combinatorial Pattern Matching*, volume 4009 of * Lecture Notes in Computer Science*, pages 330-341. Springer Verlag, Berlin, 2006.

## 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*) loglog
σ + *Sort*) and *O*(*m*) space, where *l* is the length
of an 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 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.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 2006. All rights reserved.

**Online version**

cpm06.pdf (166 Kb)

**DOI**

10.1007/11780441_30

**BIBT**_{E}X entry

@incollection{cpm06,
author = "Gerth St{\o}lting Brodal and Kanela Kaligosi and Irit Katriel and Martin Kutz",
booktitle = "Proc. 17th Annual Symposium on Combinatorial Pattern Matching",
doi = "10.1007/11780441_30",
isbn = "978-3-540-35455-0",
pages = "330-341",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Faster Algorithms for Computing Longest Common Increasing Subsequences",
volume = "4009",
year = "2006"
}