Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Faster Algorithms for Computing Longest Common Increasing Subsequences

Brodal, G. S., Kaligosi, K., Katriel, I., & Kutz, M. (2006). Faster Algorithms for Computing Longest Common Increasing Subsequences. In Combinatorial Pattern Matching, 17th Annual Symposium, CPM 2006 (pp. 330-341). Berlin, Germany: Springer.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Brodal, Gerth Stølting1, Autor           
Kaligosi, Kanela1, Autor           
Katriel, Irit1, Autor           
Kutz, Martin1, Autor           
Moshe, Lewenstein, Herausgeber
Gabriel, Valiente, Herausgeber
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2007-03-122006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 314457
Anderer: Local-ID: C1256428004B93B8-2A4A9F04F32099E6C125729600518139-Kaligosi2006b
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Barcelona, Spain
Start-/Enddatum: 2006-07-05

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Combinatorial Pattern Matching, 17th Annual Symposium, CPM 2006
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 330 - 341 Identifikator: ISBN: 3-540-35455-7

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 4009 Artikelnummer: - Start- / Endseite: - Identifikator: -