# Faster Algorithms for Computing Longest Common Increasing Subsequences

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 *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 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{*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.

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

**Online version**

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

**BIBT**_{E}X 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"
}