{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:18:31Z","timestamp":1742401111089,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T00:00:00Z","timestamp":1548115200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T00:00:00Z","timestamp":1548115200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001700","name":"Ministry of Education, Culture, Sports, Science and Technology","doi-asserted-by":"publisher","award":["JP24106004"],"award-info":[{"award-number":["JP24106004"]}],"id":[{"id":"10.13039\/501100001700","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP17H01698"],"award-info":[{"award-number":["JP17H01698"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP18K11168"],"award-info":[{"award-number":["JP18K11168"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18K11169"],"award-info":[{"award-number":["JP18K11169"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP18H04091"],"award-info":[{"award-number":["JP18H04091"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00224-018-09908-6","type":"journal-article","created":{"date-parts":[[2019,1,24]],"date-time":"2019-01-24T01:24:32Z","timestamp":1548293072000},"page":"522-541","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Space-Efficient Algorithms for Longest Increasing Subsequence"],"prefix":"10.1007","volume":"64","author":[{"given":"Masashi","family":"Kiyomi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hirotaka","family":"Ono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0087-853X","authenticated-orcid":false,"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Tarui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,1,22]]},"reference":[{"key":"9908_CR1","doi-asserted-by":"publisher","unstructured":"Ahn, H.-K., Baraldo, N., Oh, E., Silvestri, F.: A time-space trade-off for triangulations of points in the plane. In: COCOON 2017, pp 3\u201312 (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-62389-4_1","DOI":"10.1007\/978-3-319-62389-4_1"},{"issue":"4","key":"9908_CR2","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1090\/S0273-0979-99-00796-X","volume":"36","author":"D Aldous","year":"1999","unstructured":"Aldous, D., Diaconis, P.: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Am. Math. Soc. 36 (4), 413\u2013432 (1999). \nhttps:\/\/doi.org\/10.1090\/S0273-0979-99-00796-X","journal-title":"Bull. Am. Math. Soc."},{"key":"9908_CR3","doi-asserted-by":"publisher","unstructured":"Asano, T., Elmasry, A., Katajainen, J.: Priority queues and sorting for read-only data. In: TAMC 2013, pp 32\u201341 (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-38236-9_4","DOI":"10.1007\/978-3-642-38236-9_4"},{"key":"9908_CR4","doi-asserted-by":"publisher","unstructured":"Asano, T., Izumi, T., Kiyomi, M., Konagaya, M., Ono, H., Otachi, Y., Schweitzer, P., Tarui, J., Uehara, R.: Depth-first search using O(n) bits. In: ISAAC 2014, pp 553\u2013564 (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-319-13075-0_44","DOI":"10.1007\/978-3-319-13075-0_44"},{"key":"9908_CR5","doi-asserted-by":"publisher","unstructured":"Banyassady, B., Korman, M., Mulzer, W., Van Renssen, Andr\u00e9, Roeloffzen, M., Seiferth, P., Stein, Y.: Improved time-space trade-offs for computing Voronoi diagrams. In: STACS 2017, vol. 66, pp 9:1\u20139:14 (2017). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.9","DOI":"10.4230\/LIPIcs.STACS.2017.9"},{"issue":"1\u20132","key":"9908_CR6","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/S0020-0190(00)00124-1","volume":"76","author":"S Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Segal, M.: Enumerating longest increasing subsequences and patience sorting. Inf. Process. Lett. 76(1\u20132), 7\u201311 (2000). \nhttps:\/\/doi.org\/10.1016\/S0020-0190(00)00124-1","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9908_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A Borodin","year":"1982","unstructured":"Borodin, A., Cook, S.: A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11(2), 287\u2013297 (1982). \nhttps:\/\/doi.org\/10.1137\/0211022","journal-title":"SIAM J. Comput."},{"key":"9908_CR8","first-page":"B54Ab","volume":"54A","author":"A Burstein","year":"2006","unstructured":"Burstein, A., Lankham, I.: Combinatorics of patience sorting piles. S\u00e9minaire Lotharingien de Combinatoire 54A, B54Ab (2006). \nhttp:\/\/www.mat.univie.ac.at\/~slc\/wpapers\/s54Aburlank.html","journal-title":"S\u00e9minaire Lotharingien de Combinatoire"},{"key":"9908_CR9","doi-asserted-by":"publisher","unstructured":"Chakraborty, S., Satti, S.R.: Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications. In: COCOON 2017, pp 87\u201398 (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-62389-4_8","DOI":"10.1007\/978-3-319-62389-4_8"},{"issue":"1","key":"9908_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00454-006-1275-6","volume":"37","author":"TM Chan","year":"2007","unstructured":"Chan, T.M., Chen, E.Y.: Multi-pass geometric algorithms. Discret. Comput. Geom. 37(1), 79\u2013102 (2007). \nhttps:\/\/doi.org\/10.1007\/s00454-006-1275-6","journal-title":"Discret. Comput. Geom."},{"key":"9908_CR11","doi-asserted-by":"publisher","unstructured":"Cook, S.A.: Deterministic CFL\u2019s are accepted simultaneously in polynomial time and log squared space. In: STOC 1979, pp 338\u2013345 (1979), \nhttps:\/\/doi.org\/10.1145\/800135.804426","DOI":"10.1145\/800135.804426"},{"issue":"9","key":"9908_CR12","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.ic.2010.04.003","volume":"208","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Porat, E.: Fast computation of a longest increasing subsequence and application. Inf. Comput. 208(9), 1054\u20131059 (2010). \nhttps:\/\/doi.org\/10.1016\/j.ic.2010.04.003","journal-title":"Inf. Comput."},{"key":"9908_CR13","doi-asserted-by":"publisher","unstructured":"Darwish, O., Elmasry, A.: Optimal time-space tradeoff for the 2D convex-hull problem. In: ESA 2014, pp 284\u2013295 (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-662-44777-2_24","DOI":"10.1007\/978-3-662-44777-2_24"},{"key":"9908_CR14","doi-asserted-by":"publisher","unstructured":"Elmasry, A., Hagerup, T., Kammer, F.: Space-efficient basic graph algorithms. In: STACS 2015, vol. 30, pp 288\u2013301 (2015). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.288","DOI":"10.4230\/LIPIcs.STACS.2015.288"},{"issue":"6","key":"9908_CR15","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00493-014-3035-1","volume":"35","author":"F Ergun","year":"2015","unstructured":"Ergun, F., Jowhari, H.: On the monotonicity of a data stream. Combinatorica 35(6), 641\u2013653 (2015). \nhttps:\/\/doi.org\/10.1007\/s00493-014-3035-1","journal-title":"Combinatorica"},{"issue":"1","key":"9908_CR16","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(87)90002-X","volume":"34","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Upper bounds for time-space trade-offs in sorting and selection. J Comput Syst Sci 34(1), 19\u201326 (1987). \nhttps:\/\/doi.org\/10.1016\/0022-0000(87)90002-X","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"9908_CR17","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"ML Fredman","year":"1975","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Discret. Math. 11(1), 29\u201335 (1975). \nhttps:\/\/doi.org\/10.1016\/0012-365X(75)90103-X","journal-title":"Discret. Math."},{"issue":"8","key":"9908_CR18","doi-asserted-by":"publisher","first-page":"3463","DOI":"10.1137\/090770801","volume":"39","author":"A G\u00e1l","year":"2010","unstructured":"G\u00e1l, A., Gopalan, P.: Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence. SIAM J. Comput. 39(8), 3463\u20133479 (2010). \nhttps:\/\/doi.org\/10.1137\/090770801","journal-title":"SIAM J. Comput."},{"key":"9908_CR19","unstructured":"Gopalan, P., Jayram, T.S., Krauthgamer, R., Kumar, R.: Estimating the sortedness of a data stream. In: SODA 2007, pp 318\u2013327 (2007). \nhttp:\/\/dl.acm.org\/citation.cfm?id=1283417"},{"issue":"5","key":"9908_CR20","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Commun. ACM 20(5), 350\u2013353 (1977). \nhttps:\/\/doi.org\/10.1145\/359581.359603","journal-title":"Commun. ACM"},{"key":"9908_CR21","volume-title":"Communication complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"2","key":"9908_CR22","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s10878-006-7125-x","volume":"11","author":"D Liben-Nowell","year":"2006","unstructured":"Liben-Nowell, D., Vee, E., An, Z.: Finding longest increasing and common subsequences in streaming data. J. Comb. Optim. 11(2), 155\u2013175 (2006). \nhttps:\/\/doi.org\/10.1007\/s10878-006-7125-x","journal-title":"J. Comb. Optim."},{"key":"9908_CR23","doi-asserted-by":"publisher","unstructured":"Lincoln, A., Williams, V.V., Wang, J.R., Ryan Williams, R.: Deterministic time-space trade-offs for k-SUM. In: ICALP 2016, pp 58:1\u201358:14 (2016), \nhttps:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.58","DOI":"10.4230\/LIPIcs.ICALP.2016.58"},{"issue":"2","key":"9908_CR24","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/1004036","volume":"4","author":"CL Mallows","year":"1962","unstructured":"Mallows, C.L.: Problem 62-2, patience sorting. SIAM Rev. 4(2), 143\u2013149 (1962). \nhttp:\/\/www.jstor.org\/stable\/2028371","journal-title":"SIAM Rev."},{"issue":"4","key":"9908_CR25","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/1005107","volume":"5","author":"CL Mallows","year":"1963","unstructured":"Mallows, C.L.: Problem 62-2. SIAM Rev. 5(4), 375\u2013376 (1963). \nhttp:\/\/www.jstor.org\/stable\/2028347","journal-title":"SIAM Rev."},{"key":"9908_CR26","first-page":"216","volume":"9","author":"CL Mallows","year":"1973","unstructured":"Mallows, C.L.: Patience sorting. Bulletin of the Institute of Mathematics and its Applications 9, 216\u2013224 (1973)","journal-title":"Bulletin of the Institute of Mathematics and its Applications"},{"issue":"3","key":"9908_CR27","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theor. Comput. Sci. 12(3), 315\u2013323 (1980). \nhttps:\/\/doi.org\/10.1016\/0304-3975(80)90061-4","journal-title":"Theor. Comput. Sci."},{"key":"9908_CR28","doi-asserted-by":"publisher","unstructured":"Naumovitz, T., Saks, M.: A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. In: SODA 2015, pp 1252\u20131262 (2015). \nhttps:\/\/doi.org\/10.1137\/1.9781611973730.83","DOI":"10.1137\/1.9781611973730.83"},{"key":"9908_CR29","doi-asserted-by":"publisher","unstructured":"Nisan, N.: RL $\\subseteq $ SC. In: STOC 1992, pp 619\u2013623 (1992). \nhttps:\/\/doi.org\/10.1145\/129712.129772","DOI":"10.1145\/129712.129772"},{"key":"9908_CR30","doi-asserted-by":"publisher","unstructured":"Pagter, J., Rauhe, T.: Optimal time-space trade-offs for sorting. In: FOCS 1998, pp 264\u2013268 (1998). \nhttps:\/\/doi.org\/10.1109\/SFCS.1998.743455","DOI":"10.1109\/SFCS.1998.743455"},{"key":"9908_CR31","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Wrochna, M.: On space efficiency of algorithms working on structural decompositions of graphs. In: STACS 2016, vol. 47, pp 57:1\u201357:15 (2016). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.57","DOI":"10.4230\/LIPIcs.STACS.2016.57"},{"issue":"3\u20134","key":"9908_CR32","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1080\/00207169708804607","volume":"65","author":"P Ramanan","year":"1997","unstructured":"Ramanan, P.: Tight $\\Omega (n \\lg n)$ lower bound for finding a longest increasing subsequence. Int. J. Comput. Math. 65(3\u20134), 161\u2013164 (1997). \nhttps:\/\/doi.org\/10.1080\/00207169708804607","journal-title":"Int. J. Comput. Math."},{"key":"9908_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139872003","volume-title":"The surprising mathematics of longest increasing subsequences","author":"D Romik","year":"2015","unstructured":"Romik, D.: The surprising mathematics of longest increasing subsequences. Cambridge University Press, Cambridge (2015). \nhttps:\/\/doi.org\/10.1017\/CBO9781139872003"},{"key":"9908_CR34","doi-asserted-by":"publisher","unstructured":"Saks, M., Seshadhri, C.: Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. In: SODA 2013, pp 1698\u20131709 (2013). \nhttps:\/\/doi.org\/10.1137\/1.9781611973105.122","DOI":"10.1137\/1.9781611973105.122"},{"issue":"2","key":"9908_CR35","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1137\/130942152","volume":"46","author":"M Saks","year":"2017","unstructured":"Saks, M., Seshadhri, C: Estimating the longest increasing sequence in polylogarithmic time. SIAM J. Comput. 46(2), 774\u2013823 (2017). \nhttps:\/\/doi.org\/10.1137\/130942152","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9908_CR36","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970). \nhttps:\/\/doi.org\/10.1016\/S0022-0000(70)80006-X","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9908_CR37","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4153\/CJM-1961-015-3","volume":"13","author":"C Schensted","year":"1961","unstructured":"Schensted, C.: Longest increasing and decreasing subsequences. Can. J. Math. 13(2), 179\u2013191 (1961). \nhttps:\/\/doi.org\/10.4153\/CJM-1961-015-3","journal-title":"Can. J. Math."},{"key":"9908_CR38","unstructured":"Su, X., Woodruff, D.P.: The communication and streaming complexity of computing the longest common and increasing subsequences. In: SODA 2007, pp 336\u2013345 (2007). \nhttp:\/\/dl.acm.org\/citation.cfm?id=1283383.1283419"},{"key":"9908_CR39","doi-asserted-by":"publisher","unstructured":"Wang, J.R.: Space-efficient randomized algorithms for K-SUM. In: ESA 2014, pp 810\u2013829 (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-662-44777-2_67","DOI":"10.1007\/978-3-662-44777-2_67"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-09908-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-09908-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-09908-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T05:38:29Z","timestamp":1589693909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-09908-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,22]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9908"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-09908-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,1,22]]},"assertion":[{"value":"22 January 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}