Name
Abstract | ||
|---|---|---|
We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths n and m, where m=n, we present an algorithm with an output-dependent expected running time of O((m+n@?)loglog@s+Sort) and O(m) space, where @? is the length of an LCIS, @s 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(min{m+nlogn,mloglogm})-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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jda.2011.03.013 | J. Discrete Algorithms |
Keywords | DocType | Volume |
faster algorithm,longest common weakly-increasing,comparable speedup,3-letter alphabet case,longest common increasing subsequence,small alphabet,time algorithm,longest common subsequence problem,present algorithm,factor k,input sequence,data structure,longest common subsequence,van emde boas trees | Journal | 9 |
Issue | ISSN | Citations |
4 | 1570-8667 | 6 |
PageRank | References | Authors |
0.54 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Kutz | 1 | 99 | 6.83 |
| Gerth Stølting Brodal | 2 | 1399 | 86.30 |
| Kanela Kaligosi | 3 | 39 | 2.96 |
| Irit Katriel | 4 | 176 | 13.72 |