Please note that eDoc will be permanently shut down in the first quarter of 2021! Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

 Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 314457.0, MPI für Informatik / Algorithms and Complexity Group
Faster Algorithms for Computing Longest Common Increasing Subsequences
Authors:
Editors:
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):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
(YYYY-MM-DD):
2006-07-05
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
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.
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 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.
Last Change of the Resource (YYYY-MM-DD):2007-03-12
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-2A4A9F04F32099E6C125729600518139-...
ISBN:3-540-35455-7
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.