We present algorithms for finding a longest common increasing
subsequence of two or more input sequences. For two sequences of lengths
![$m$](Abs/img1.gif)
and
![$n$](Abs/img2.gif)
, where
![$m\ge n$](Abs/img3.gif)
, we present an algorithm with an output-dependent
expected running time of
![$O((m+n\ell) \log\log \sigma + \mathit{Sort})$](Abs/img4.gif)
and
![$O(m)$](Abs/img5.gif)
space, where
![$\ell$](Abs/img6.gif)
is the length of a LCIS,
![$\sigma$](Abs/img7.gif)
is the size of
the alphabet, and
![$\mathit{Sort}$](Abs/img8.gif)
is the time to sort each input
sequence.For
![$k\ge 3$](Abs/img9.gif)
length-
![$n$](Abs/img2.gif)
sequences we present an algorithm
running time
![$O(\min\{kr^2,r\log^{k-1}r\}+\mathit{Sort})$](Abs/img10.gif)
, which improves the
previous best bound by more than a factor
![$k$](Abs/img11.gif)
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)$](Abs/img12.gif)
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.