MPI-INF D1 Publications: Proceedings Article: Faster Algorithms for Computing Longest Common Increasing Subsequences

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

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:


(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 $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

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