Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 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
 Conference URL:: http://www.lsi.upc.edu/~cpm2006/ Downloading URL: 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 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+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},