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:








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 mn, we present an algorithm with an output-dependent expected running time of $O((m+n\ell) \log\log \sigma + {\ensuremath{\mathit{Sort}}})$and O(m) space, where ℓ is the length of an LCIS, σ is the size of the alphabet, and ${\ensuremath{\mathit{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(m+nlogn)-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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for 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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section