Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2019) |
last year
(2018) |
two years ago
(2017) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Brodal, Gerth Stølting
Kaligosi, Kanela
Katriel, Irit
Kutz, Martin
dblp
dblp
dblp
dblp
Not MPG Author(s):
Brodal, Gerth Stølting
Katriel, Irit
Editor(s):
Moshe, Lewenstein
Gabriel, Valiente
dblp
dblp
Not MPII Editor(s):
Moshe, Lewenstein
Gabriel, Valiente
BibTeX cite key*:
Kaligosi2006b
Title, Booktitle
Title*:
Faster Algorithms for Computing Longest Common Increasing Subsequences
Booktitle*:
Combinatorial Pattern Matching, 17th Annual Symposium, CPM 2006
Event, URLs
URL of the conference:
http://www.lsi.upc.edu/~cpm2006/
URL for downloading the paper:
http://www.springerlink.com/content/m24861t2425k0251/fulltext.pdf
Event Address*:
Barcelona, Spain
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
5 July 2006
Event End Date:
7 July 2006
Publisher
Name*:
Springer
URL:
http://www.springer.com/west/home?SGWID=4-102-0-0-0
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4009
Number:
Month:
Pages:
330-341
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
3-540-35455-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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\ge n$, we present an algorithm with an
output-dependent expected running time of $O((m+n\ell) \log\log
\sigma + \cleanSort)$ and $O(m)$ space, where $\ell$ is the length
of an LCIS, $\sigma$ is the size of the alphabet, and $\cleanSort$ is
the time to sort each input sequence.
For $k\ge 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.
URL for the Abstract:
http://dx.doi.org/10.1007/11780441_30
Personal Comments:
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
and
O
(
m
) space, where ℓ is the length of an LCIS,
σ
is the size of the alphabet, and
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.
Download
Access Level:
Public
Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort
BibTeX Entry:
@INPROCEEDINGS
{
Kaligosi2006b
,
AUTHOR = {Brodal, Gerth Stølting and Kaligosi, Kanela and Katriel, Irit and Kutz, Martin},
EDITOR = {Moshe, Lewenstein and Gabriel, Valiente},
TITLE = {Faster Algorithms for Computing Longest Common Increasing Subsequences},
BOOKTITLE = {Combinatorial Pattern Matching, 17th Annual Symposium, CPM 2006},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4009},
PAGES = {330--341},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Barcelona, Spain},
ISBN = {3-540-35455-7},
}
Entry last modified by Christine Kiesel, 03/12/2007
Edit History (please click the blue arrow to see the details)
Edit History (please click the blue arrow to see the details)
Editor(s)
Kanela Kaligosi
Created
03/06/2007 03:50:14 PM
Revisions
2.
1.
0.
Editor(s)
Christine Kiesel
Kanela Kaligosi
Kanela Kaligosi
Edit Dates
12.03.2007 07:29:36
03/06/2007 03:50:51 PM
03/06/2007 03:50:15 PM
Attachment Section
Attachment Section