A copy of this work was available on the public web and has been preserved in the Wayback Machine. The capture dates from 2012; you can also visit the original URL.
The file type is `application/pdf`

.

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

2005
*
BRICS Report Series
*

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) log log sigma + Sort) and O(m) space, where l is the length of an LCIS, sigma is the size of the alphabet, and 'Sort' is the time to sort each input sequence.<br /> <br />For k >= 3 length-n sequences we present an algorithm running time O(min{k r^2, r

doi:10.7146/brics.v12i37.21904
fatcat:elz6sg2uzfgt7cb6kdx6n4qjti