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

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          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: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 (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:MPI für Informatik/Algorithms and Complexity Group
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.