ID:
314457.0,
MPI für Informatik / Algorithms and Complexity Group 
Faster Algorithms for Computing Longest Common Increasing Subsequences 
Authors:  Brodal, Gerth Stølting; Kaligosi, Kanela; Katriel, Irit; Kutz, Martin 
Editors:  Moshe, Lewenstein; Gabriel, Valiente 
Language:  English 
Publisher:  Springer 
Place of Publication:  Berlin, Germany 
Date of Publication (YYYYMMDD):  2006 
Title of Proceedings:  Combinatorial Pattern Matching, 17th Annual Symposium, CPM 2006 
Start Page:  330 
End Page:  341 
Title of Series:  Lecture Notes in Computer Science 
Place of Conference/Meeting:  Barcelona, Spain 
(Start) Date of Conference/Meeting (YYYYMMDD):  20060705 
Audience:  Experts Only 
Intended Educational Use:  No 
Abstract / Description:  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 outputdependent 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 weaklyincreasing (or nondecreasing) subsequences (LCWIS), for which we present an $O(m+n\log n)$time algorithm for the 3letter alphabet case. For the extensively studied longest common subsequence problem, comparable speedups have not been achieved for small alphabets. 
Comment of the Author/Creator:  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 outputdependent 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 lengthn 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 weaklyincreasing (or nondecreasing) subsequences (LCWIS), for which we present an O(m+nlogn)time algorithm for the 3letter alphabet case. For the extensively studied longest common subsequence problem, comparable speedups have not been achieved for small alphabets. 
Last Change of the Resource (YYYYMMDD):  20070312 
External Publication Status:  published 
Document Type:  ConferencePaper 
Communicated by:  Kurt Mehlhorn 
Affiliations:  MPI für Informatik/Algorithms and Complexity Group

Identifiers:  LOCALID:C1256428004B93B82A4A9F04F32099E6C125729600518139... ISBN:3540354557 
