On Some Variants of the Longest Increasing Subsequence Problem

• Autorzy: Deorowicz S.

Warianty tytułu

PL

O pewnych wariantach problemu wyznaczania najdłuższego rosnącego podciągu

• Języki publikacji: EN

Abstrakty

EN

The problem of finding a longest increasing subsequence (LIS) is a well known task in sequence processing. There are many variants of the basic task. We discuss a recently introduced variant of LIS, a minimal height longest increasing subsequence problem and propose a new algorithm for it, which improves its time complexity. Moreover, we define a family of similar problems and introduce algorithms solving them.

PL

Problem wyznaczania najdłuższego rosnącego podciągu (ang. longest increasing subsequence, LIS) jest jednym z problemów w przetwarzaniu ciągów. W artykule dyskutowany jest jeden z jego wariantów, a mianowicie problem wyznaczania najdłuższego rosnącego podciągu o minimalnej wysokości. Zaprezentowany algorytm dla tego problemu oferuje złożoność czasową lepsza niż najszybszy opisany do tej pory w literaturze algorytm. Ponadto w pracy zdefiniowano rodzinę podobnych problemów, dla których zaproponowano optymalne algorytmy ich rozwiazywania.

Słowa kluczowe

EN

longest increasing subsequence

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2009
• Tom: Vol. 21, No. 3-4
• Strony: 135--148
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Deorowicz S.

• Silesian University of Technology

Bibliografia

• 1. M.H. Albert, M.D. Atkinson, D. Nussbaum, J.-R. Sack, N. Santoro: On the longest increasing subsequence of a circular list, Information Processing Letters 101, pp. 55–59, 2007.
• 2. D. Aldous, P. Diaconis: Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem, Bulletin of the AMS 36, pp. 413–432, 1999.
• 3. M.H. Albert, A. Golynski, A.M. Hamel, A. López-Ortiz, S.S. Rao, M.A. Safari: Longest increasing subsequences in sliding windows, Theoretical Computer Science 321, pp. 405–414, 2004.
• 4. E. Chen, L. Yang, H. Yuan: Longest increasing subsequences in windows based on canonical antichain partition, Theoretical Computer Science 378(3), pp. 223–236, 2007.
• 5. S. Deorowicz: An algorithm for solving the longest increasing circular subsequence problem, Information Processing Letters 109(12), pp. 630–634, 2009.
• 6. A.L. Delcher, S. Kasif, R.D. Fleischmann, J. Peterson, O. White, S.L. Salzberg: Alignment of while genomes, Nucleic Acids Research 27(11), pp. 2369–2376, 1999.
• 7. P. van Emde Boas, R. Kaas, E. Zijlstra: Design and implementation of an efficient priority queue, Mathematical Systems Theory 10, pp. 99–127, 1977.
• 8. M.L. Fredman: On computing the length of longest increasing subsequences, Discrete Mathematics 11, pp. 29–35, 1975.
• 9. D. Gusfield: Algorithms on strings, trees, and sequences, Cambridge University Press, USA, 1999.
• 10. G. Jacobson, K.-P. Vo: Heaviest increasing/common subsequence problems, Lecture Notes in Computer Science 644, pp. 52–66, 1992.
• 11. C.-T. Tseng, C.-B. Yang, and H.-Y. Ann: Minimal Height and Sequence Constrained Longest Increasing Subsequence, Journal of Internet Technology 10(2), pp. 173–178, 2009.
• 12.I-H. Yang, Y-C. Chen: Fast algorithms for the constrained longest increasing subsequence problems, In Proceedings of the 25thWorkshop on Combinatorial Mathematics and Computation Theory, Hsinchu Hsien, Taiwan, April 25–26, pp. 226–231, 2008.