Longest increasing subsequences in sliding windows

Keywords

Subsequence, Sliding window protocol, Longest increasing subsequence, Sequence (biology), Generalization

References

• The art of computer programming, volume 3: (2nd ed.) sorting and searchingDonald E. Knuth — 1998
• The Robinson-Schensted and Schützenberger algorithms, an elementary approachMarc Van Leeuwen — 1995
• Distributed Streams Algorithms for Sliding WindowsPhillip B. Gibbons, Srikanta Tirthapura — 2002
• Maintaining Stream Statistics over Sliding WindowsMayur Datar, Aristides Gionis, Piotr Indyk — 2002
• Maintaining stream statistics over sliding windows: (extended abstract)Mayur Datar, Aristides Gionis, Piotr Indyk — 2002
• Enumerating longest increasing subsequences and patience sortingSergei Bespamyatnikh, Michael Segal — 2000
• New clique and independent set algorithms for circle graphsAlberto Apostolico, Mikhail J. Atallah, Susanne E. Hambrusch — 1992
• A fast algorithm for computing longest common subsequencesJames Hunt, Thomas G. Szymanski — 1977
• Efficient Algorithms for the Maximum Weight Clique and Maximum Weight Independent Set Problems on Permutation GraphsMaw‐Shang Chang, Fu–Hsing Wang — 1992
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theoremDavid Aldous, Persi Diaconis — 1999
• Design and implementation of an efficient priority queuePeter Emde Boas, R. Kaas, E.E. Zijlstra — 1976
• Hydrodynamical methods for analyzing longest increasing subsequencesPiet Groeneboom — 2002
• Alignment of whole genomes.Arthur L. Delcher, Simon Kasif, R. D. Fleischmann — 1999
• PERMUTATIONS, MATRICES, AND GENERALIZED YOUNG TABLEAUXDonald Knuth — 1970
• On the Representations of the Symmetric GroupG. de B. Robinson — 1938
• The Art of Computer ProgrammingG.E. Whitesides — 1968
• Longest Increasing and Decreasing SubsequencesC. Schensted — 1961
• The Symmetric GroupT. Inui, Y. Tanabe, Y. Onodera — 1990
• Representations of the Symmetric GroupB. Sagan — 2001
• The art of computer programming: sorting and searching (volume 3)D. Knuth — 1973

Cited by

• Semi-local longest common subsequences and maximum cliques in circle graphsAlexander Tiskin — 2006
• Window-chained longest common subsequence: Common event matching in sequencesChunyao Song, Tingjian Ge — 2015
• A Set Probability Technique for Detecting Relative Time Order Across Multiple NeuronsAnne C. Smith, Peter Smith — 2006
• An algorithm for solving the longest increasing circular subsequence problemSebastian Deorowicz — 2009
• The longest almost-increasing subsequenceAmr Elmasry — 2010
• On the longest increasing subsequence of a circular listMichael Albert, M. D. Atkinson, Doron Nussbaum — 2007
• Sekwencyjne i równolegle algorytmy znajdowania podciągówSebastian Deorowicz — 2010
• Semi-local String Comparison: Algorithmic Techniques and ApplicationsAlexander Tiskin — 2007
• Longest increasing subsequences in windows based on canonical antichain partitionErdong Chen, Linji Yang, Hao Yuan — 2005
• A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window ProblemSebastian Deorowicz — 2013
• Efficient Summing over Sliding WindowsRan Ben Basat — 2016
• LIS using backtracking and branch-and-bound approachesSeema Rani, Dharmveer Singh Rajpoot — 2016
• On Differentially Private Longest Increasing Subsequence Computation in Data StreamLuca Bonomi, Li Xiong — 2016
• Minimum Height and Sequence Constrained Longest Increasing SubsequenceChiou-Ting Tseng, Chang‐Biau Yang, Hsing-Yen Ann — 2009
• Longest Increasing Subsequence Computation over Streaming SequencesYouhuan Li, Lei Zou, Huaming Zhang — 2018
• Tracking maximum ascending subsequences in sequences of partially ordered dataTon Kloks, Richard B. Tan, Jan Van Leeuwen — 2017
• Improvised divide and conquer approach for the LIS problemSeema Rani, Dharmveer Singh Rajpoot — 2018
• On-line scheduling with monotone subsequence constraintsKelin Luo, Yinfeng Xu, Huili Zhang — 2019
• Succinct Summing over Sliding WindowsRan Ben Basat, Gil Einziger, Roy Friedman — 2018
• Sequential DependenciesLukasz Golab, Howard Karloff, Flip Korn — 2009

Related papers

• Bit-Parallel Algorithm for the Constrained Longest Common Subsequence ProblemDeorowiczSebastian — 2010
• Longest (Sub-)Periodic SubsequenceHideo Bannai, I Tomohiro, Dominik Köppl — 2022
• A fast algorithm for computing a longest common increasing subsequenceI‐Hsuan Yang, Chien-Pin Huang, Kun‐Mao Chao — 2005
• Computing The Longest Common Almost-Increasing SubsequenceMohammad Tawhidul Hasan Bhuiyan, Muhammad Rashed Alam, M. Sohel Rahman — 2022
• What Do a Longest Increasing Subsequence and a Longest Decreasing Subsequence Know about Each Other?Elizabeth J. Itskovich, Vadim E. Levit — 2019
• A Fast Randomized Algorithm for Finding the Maximal Common SubsequencesJin Cao, Dewei Zhong — 2020
• A Fast Algorithm for Finding a Maximal Common Subsequence of Multiple StringsMiyuji Hirota, Yoshifumi Sakai — 2023