Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition
作者： Erdong Chen , Hao Yuan , Linji Yang
DOI: 10.1007/11602613_114
关键词:
摘要: We consider the Lisw problem, which is to find longest increasing subsequences (LIS) in a sliding window of fixed-size w over sequence π1π2...πn. Formally, it LIS for every set SFIX ={π〈i+1, i+w〉|0≤i≤n−w}∪{π〈1, i〉, π〈n−i, n〉|i
springer.com
core.ac.uk
springerlink.com参考文章(14)
Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching Addison Wesley Longman Publishing Co., Inc.. ,(1998)
Alberto Apostolico, Mikhail J. Atallah, Susanne Hambrusch, New clique and independent set algorithms for circle graphs: Discrete Applied Mathematics 36 (1992) 1–24 Discrete Applied Mathematics. ,vol. 41, pp. 179- 180 ,(1993) , 10.1016/0166-218X(93)90038-P
Sridhar Rajagopalan, Prabhakar Raghavan, Monika R. Henzinger, Computing on data streams External memory algorithms. pp. 107- 118 ,(1999)
Sergei Bespamyatnikh, Michael Segal, Enumerating longest increasing subsequences and patience sorting Information Processing Letters. ,vol. 76, pp. 7- 11 ,(2000) , 10.1016/S0020-0190(00)00124-1
Alberto Apostolico, Mikhail J. Atallah, Susanne E. Hambrusch, New clique and independent set algorithms for circle graphs Discrete Applied Mathematics. ,vol. 36, pp. 1- 24 ,(1992) , 10.1016/0166-218X(92)90200-T
C. Schensted, Longest Increasing and Decreasing Subsequences Canadian Journal of Mathematics. ,vol. 13, pp. 299- 311 ,(1961) , 10.1007/978-0-8176-4842-8_21
Temple F Smith, Michael S Waterman, Comparison of biosequences Advances in Applied Mathematics. ,vol. 2, pp. 482- 489 ,(1981) , 10.1016/0196-8858(81)90046-4
David Liben-Nowell, Erik Vee, An Zhu, None, Finding longest increasing and common subsequences in streaming data Journal of Combinatorial Optimization. ,vol. 11, pp. 155- 175 ,(2006) , 10.1007/S10878-006-7125-X
Michael L. Fredman, On computing the length of longest increasing subsequences Discrete Mathematics. ,vol. 11, pp. 29- 35 ,(1975) , 10.1016/0012-365X(75)90103-X
Stefan Felsner, Lorenz Wernisch, Maximum k -Chains in Planar Point Sets: Combinatorial Structure and Algorithms SIAM Journal on Computing. ,vol. 28, pp. 192- 209 ,(1999) , 10.1137/S0097539794266171