A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem

Sebastian Deorowicz

Abstract

A longest increasing subsequence problem (LIS) is a well-known combinatorial problem with applications mainly in bioinformatics, where it is used in various projects on DNA sequences. Recently, a number of generalisations of this problem were proposed. One of them is to find an LIS among all fixed-size windows of the input sequence (LISW). We propose an algorithm for the LISW problem based on cover representation of the sequence that outperforms the existing methods for some class of the input sequences.

Keywords

MSC

68W05

Cite this article

@article{cai-11170,
  author  = {Sebastian Deorowicz},
  title   = {A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem},
  journal = {Computing and Informatics},
  volume  = {31},
  number  = {6},
  pages   = {1217--1233},
  year    = {2012},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2012/6/a-cover-merging-based-algorithm-for-the-longest-increasing-subsequence-in-a-sliding-window-problem/}
}

Download .bib

TY  - JOUR
AU  - Sebastian Deorowicz
TI  - A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem
JO  - Computing and Informatics
VL  - 31
IS  - 6
SP  - 1217
EP  - 1233
PY  - 2012
SN  - 1335-9150
UR  - https://cai.type.sk/content/2012/6/a-cover-merging-based-algorithm-for-the-longest-increasing-subsequence-in-a-sliding-window-problem/
KW  - Longest increasing subsequence
KW  - sliding window
KW  - pattern matching
ER  -

Download .ris

Deorowicz, S. (2012). A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem. Computing and Informatics, 31(6), 1217–1233. https://cai.type.sk/content/2012/6/a-cover-merging-based-algorithm-for-the-longest-increasing-subsequence-in-a-sliding-window-problem/

Download .txt