A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem
Sebastian Deorowicz; Institute of Informatics, Silesian University of Technology, Gliwice
Computing and Informatics, Tome 31 (2013) no. 6, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2013-01-24
Classification:  Longest increasing subsequence, sliding window, pattern matching,  68W05 
@article{cai1305,
     author = {Sebastian Deorowicz; Institute of Informatics, Silesian University of Technology, Gliwice},
     title = {A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem},
     journal = {Computing and Informatics},
     volume = {31},
     number = {6},
     year = {2013},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai1305}
}

Sebastian Deorowicz; Institute of Informatics, Silesian University of Technology, Gliwice. A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem. Computing and Informatics, Tome 31 (2013) no. 6, . http://gdmltest.u-ga.fr/item/cai1305/