de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Faster Algorithms for Computing Longest Common Increasing Subsequences

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44187

Brodal,  Gerth Stølting
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44722

Kaligosi,  Kanela
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44744

Katriel,  Irit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44874

Kutz,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-22CB-5
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.