Academic literature on the topic 'Longest increasing subsequences'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Longest increasing subsequences.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Longest increasing subsequences"
Russo, Luıs, and Alexandre Francisco. "Small Longest Tandem Scattered Subsequences." Scientific Annals of Computer Science 31, no. 1 (August 9, 2021): 79–110. http://dx.doi.org/10.7561/sacs.2021.1.79.
Full textAlbert, Michael H., Alexander Golynski, Angèle M. Hamel, Alejandro López-Ortiz, S. Srinivasa Rao, and Mohammad Ali Safari. "Longest increasing subsequences in sliding windows." Theoretical Computer Science 321, no. 2-3 (August 2004): 405–14. http://dx.doi.org/10.1016/j.tcs.2004.03.057.
Full textBóna, Miklós, Marie-Louise Lackner, and Bruce E. Sagan. "Longest Increasing Subsequences and Log Concavity." Annals of Combinatorics 21, no. 4 (August 19, 2017): 535–49. http://dx.doi.org/10.1007/s00026-017-0365-x.
Full textGroeneboom, Piet. "Hydrodynamical methods for analyzing longest increasing subsequences." Journal of Computational and Applied Mathematics 142, no. 1 (May 2002): 83–105. http://dx.doi.org/10.1016/s0377-0427(01)00461-7.
Full textBespamyatnikh, Sergei, and Michael Segal. "Enumerating longest increasing subsequences and patience sorting." Information Processing Letters 76, no. 1-2 (November 2000): 7–11. http://dx.doi.org/10.1016/s0020-0190(00)00124-1.
Full textHe, Xiaozhou, and Yinfeng Xu. "The longest commonly positioned increasing subsequences problem." Journal of Combinatorial Optimization 35, no. 2 (September 9, 2017): 331–40. http://dx.doi.org/10.1007/s10878-017-0170-9.
Full textDEUSCHEL, JEAN-DOMINIQUE, and OFER ZEITOUNI. "On Increasing Subsequences of I.I.D. Samples." Combinatorics, Probability and Computing 8, no. 3 (May 1999): 247–63. http://dx.doi.org/10.1017/s0963548399003776.
Full textLi, Youhuan, Lei Zou, Huaming Zhang, and Dongyan Zhao. "Computing longest increasing subsequences over sequential data streams." Proceedings of the VLDB Endowment 10, no. 3 (November 2016): 181–92. http://dx.doi.org/10.14778/3021924.3021934.
Full textAldous, D., and P. Diaconis. "Hammersley's interacting particle process and longest increasing subsequences." Probability Theory and Related Fields 103, no. 2 (June 1995): 199–213. http://dx.doi.org/10.1007/bf01204214.
Full textKutz, Martin, Gerth Stølting Brodal, Kanela Kaligosi, and Irit Katriel. "Faster algorithms for computing longest common increasing subsequences." Journal of Discrete Algorithms 9, no. 4 (December 2011): 314–25. http://dx.doi.org/10.1016/j.jda.2011.03.013.
Full textDissertations / Theses on the topic "Longest increasing subsequences"
Boyer, Alexandre. "Bidimensional stationarity of random models in the plane." Thesis, université Paris-Saclay, 2022. http://www.theses.fr/2022UPASM011.
Full textIn this PhD thesis, three models have been independently studied. They all have in common to be random models defined in the plane and having a two-dimensional stationarity property. The first one is Hammersley’s stationary model in the quarter plane, introduced and studied by Cator and Groeneboom. We present here a probablistic proof the Gaussian fluctuations in the non-critical case. The second model can be seen as a stationary modification ofO’Connell-Yor’s problem. The proof of its stationarity is obtained by introducing a discretisation of this model, by proving its stationairty and then by observing that this stationarity is preserved in the limit. Finally, the third model is a general class of random systems of horizontal and vertical weighted broken lines on the quarter plane whose distribution are proved to be reversible. This class of systems generalizes several classical processes of the same kind. The noveltycomes here from the introduction of a weight associated with each line
Liben-Nowell, David, Erik Vee, and An Zhu. "Finding Longest Increasing and Common Subsequences in Streaming Data." 2003. http://hdl.handle.net/1721.1/30435.
Full textTseng, Chiou-Ting, and 曾球庭. "Variants of the Constrained Longest Common and Longest Increasing Subsequence Problems." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/21836302143691115299.
Full text國立中山大學
資訊工程學系研究所
101
Given two strings A = a1a2a3...am and B = b1b2b3...bn, the longest common subsequence (LCS) problem is that of finding the longest common part of A and B by deleting zero or more characters from A and B. Given a string S = a1a2a3...am, composed of comparable elements, the longest increasing subsequence (LIS) problem is that of finding a subsequence of S such that the subsequence is increasing and its length is maximal. The constrained LCS (CLCS) or constrained LIS (CLIS) problem is that of finding the longest subsequence satisfying the given constraint C. In this dissertation, we propose and solve several variants of the LCS and LIS problems, which are (1) the sequential substring CLCS problem, (2) the string-exclusion CLCS problem, (3) the minimum height LIS problem and (4) the sequence constrained LIS problem. Given an ordered set of constraint substrings (C^1, C^2,... , C^h) with total length r, the sequential substring CLCS problem is that of finding the CLCS of A and B containing all constraint substrings as substrings and the order of them are retained. This problem has two variants, depending on whether the strings cannot overlap or may overlap. We propose algorithms with O(mnh + (m + n)(|Σ| + r)) and O(mnr + (m + n)|Σ|) time for the two variants, respectively. When there is a single constraint substring, i.e., the string-inclusion CLCS problem, our algorithm runs in O(mn+(m+n)(|Σ|+r)) time which improves the previous O(mnr)-time algorithm. The string-exclusion CLCS is that of finding the LCS excluding C as a substring. We propose an O(mnr)-time algorithm for it even if there are multiple constraints with total length r. The minimum height LIS problem is that of finding the ones with minimum difference between the first element and the last element among the LIS''s. We propose an algorithm with O(n log n)-time and O(n)-space to solve it. The sequence constrained LIS problem is that of finding the CLIS of A containing C. We propose two variants of this problem, without or with preprocessing. We solve the first one with time complexity O(n log(n + |C|)). For the second one, after an O(n^2 log log n)-time preprocessing, we can answer one query in O(|C| + |OUTPUT|) time where OUTPUT is the answer to the query.
Tseng, Chiou-Ting, and 曾球庭. "Finding the Longest Increasing Subsequence of Every Substring." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/03785018700384990529.
Full text國立中山大學
資訊工程學系研究所
94
Given a string S = {a1, a2, a3, ..., an}, the longest increasing subsequence (LIS) problem is to find a subsequence of the given string such that the subsequence is increasing and its length is maximal. In a previous result, to find the longest increasing subsequences of each sliding window with a fixed size w of a given string with length n can be solved in O(w log log n+OUTPUT) time, where O(w log log n+ w^2) time is taken for preprocessing and OUTPUT is the sum of all output lengths. In this thesis, we solve the problem for finding the longest increasing subsequence of every substring of S. With the straightforward implementation of the previous result, the time required for the preprocessing would be O(n^3). We modify the data structure used in the algorithm, hence the required preprocessing time is improved to O(n^2). The time required for the report stage is linear to the size of the output. In other words, our algorithm can find the LIS of every substring in O(n^2+OUTPUT) time. If the LIS''s of all substrings are desired to be reported, since there are O(n^2) substrings totally in a given string with length n, our algorithm is optimal.
Tsou, Hsiang-Yu, and 鄒翔宇. "A Study on the Longest Common Increasing Subsequence Problem." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/15994031253597300578.
Full textLin, Guan-yu, and 林冠宇. "Finding a Longest Increasing Subsequence of Complete Bipartite Graphs." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/88q56j.
Full text國立臺灣科技大學
資訊管理系
100
In this thesis, we present an -time algorithm for finding a longest increasing subsequence of complete bipartite graphs where m is more number of vertex set than another. Let be an integer sequence. The longest increasing subsequence problem is to find an increasing subsequence of with the longest length. By regarding as a weight sequence of the vertices in a path, we can redefine the longest increasing subsequence problem on graphs as follows. Let be a graph in which every vertex has a weight . A longest increasing subsequence of is a longest increasing weight subsequence of . Our research is to find a longest increasing subsequence of complete bipartite graphs.
Lo, Shou-Fu, and 羅守莆. "A Diagonal Algorithm for the Longest Common Increasing Subsequence Problem." Thesis, 2018. http://ndltd.ncl.edu.tw/handle/c4377t.
Full text國立中山大學
資訊工程學系研究所
106
The longest common increasing subsequences (LCIS) problem is to find out a common increasing subsequence with the maximal length of two given sequences. In this thesis, we propose an algorithm for solving the LCIS problem in O((n+L(m-L))loglog |Σ|) time, where m and n denote the lengths of A and B, respectively, m≤n, L denotes the LCIS length, andΣdenotes the alphabet set. The main idea of our algorithm is to extend the answer from some previously feasible solutions, in which the domination operation is invoked. To accomplish the extension and domination operations, the data structure of van Emde Boas tree is utilized. From the time complexity, it is obvious that our algorithm is extremely efficient when L is very small or very large. Some experiments are executed to show the efficiency of our algorithm.
Al-Meanazel, Ayat. "The Distribution of the Length of the Longest Increasing Subsequence in Random Permutations of Arbitrary Multi-sets." 2015. http://hdl.handle.net/1993/30872.
Full textFebruary 2016
Books on the topic "Longest increasing subsequences"
The surprising mathematics of longest increasing subsequences. Cambridge University Press, 2015.
Find full textBook chapters on the topic "Longest increasing subsequences"
Schensted, C. "Longest Increasing and Decreasing Subsequences." In Classic Papers in Combinatorics, 299–311. Boston, MA: Birkhäuser Boston, 2009. http://dx.doi.org/10.1007/978-0-8176-4842-8_21.
Full textBrodal, Gerth Stølting, Kanela Kaligosi, Irit Katriel, and Martin Kutz. "Faster Algorithms for Computing Longest Common Increasing Subsequences." In Combinatorial Pattern Matching, 330–41. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11780441_30.
Full textKrusche, Peter, and Alexander Tiskin. "Parallel Longest Increasing Subsequences in Scalable Time and Memory." In Parallel Processing and Applied Mathematics, 176–85. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14390-8_19.
Full textLiben-Nowell, David, Erik Vee, and An Zhu. "Finding Longest Increasing and Common Subsequences in Streaming Data." In Lecture Notes in Computer Science, 263–72. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11533719_28.
Full textLin, Chun, Chao-Yuan Huang, and Ming-Jer Tsai. "An Efficient Algorithm for Enumerating Longest Common Increasing Subsequences." In Lecture Notes in Computer Science, 25–36. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-89543-3_3.
Full textChen, Erdong, Hao Yuan, and Linji Yang. "Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition." In Algorithms and Computation, 1153–62. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11602613_114.
Full textLavanya, Balaraja, and Annamalai Murugan. "Multidimensional Longest Increasing Subsequences and Its Variants Discovery Using DNA Operations." In Mining Intelligence and Knowledge Exploration, 444–52. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-319-03844-5_45.
Full textElmasry, Amr. "The Longest Almost-Increasing Subsequence." In Lecture Notes in Computer Science, 338–47. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14031-0_37.
Full textGeissmann, Barbara. "Longest Increasing Subsequence Under Persistent Comparison Errors." In Approximation and Online Algorithms, 259–76. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-04693-4_16.
Full textMitzenmacher, Michael, and Saeed Seddighin. "Improved Sublinear Time Algorithm for Longest Increasing Subsequence." In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 1934–47. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2021. http://dx.doi.org/10.1137/1.9781611976465.115.
Full textConference papers on the topic "Longest increasing subsequences"
Lee, Inbok, and Sung-il Oh. "Mining intrusion detection rules with longest increasing subsequences of q-grams." In RACS '17: International Conference on Research in Adaptive and Convergent Systems. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3129676.3129724.
Full textKociumaka, Tomasz, and Saeed Seddighin. "Improved dynamic algorithms for longest increasing subsequence." In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3406325.3451026.
Full textSeme, David, and Sideny Youlou. "An Efficient Parallel Algorithm for the Longest Increasing Subsequence Problem on a LARPBS." In Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007). IEEE, 2007. http://dx.doi.org/10.1109/pdcat.2007.74.
Full textSeme, David, and Sideny Youlou. "An Efficient Parallel Algorithm for the Longest Increasing Subsequence Problem on a LARPBS." In Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007). IEEE, 2007. http://dx.doi.org/10.1109/pdcat.2007.4420178.
Full textGal, Anna, and Parikshit Gopalan. "Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence." In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07). IEEE, 2007. http://dx.doi.org/10.1109/focs.2007.4389501.
Full textGal, Anna, and Parikshit Gopalan. "Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence." In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07). IEEE, 2007. http://dx.doi.org/10.1109/focs.2007.54.
Full textCROCHEMORE, MAXIME, and ELY PORAT. "Computing a Longest Increasing Subsequence of Length k in Time O ( n log log k )." In Visions of Computer Science - BCS International Academic Conference. BCS Learning & Development, 2008. http://dx.doi.org/10.14236/ewic/vocs2008.7.
Full text