{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:39Z","timestamp":1792111479064,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":19,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_586","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:06Z","timestamp":1461268986000},"page":"1260-1264","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Memory-Constrained Algorithms"],"prefix":"10.1007","author":[{"given":"Matias","family":"Korman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"586_CR13305","first-page":"218","volume-title":"Random walks, universal traversal sequences, and the complexity of maze problems","author":"R Aleliunas","year":"1979","unstructured":"Aleliunas R, Karp RM, Lipton R, Lovasz L, Rackoff C (1979) Random walks, universal traversal sequences, and the complexity of maze problems. In: FOCS, San Juan, pp\u00a0218\u2013223"},{"issue":"2","key":"586_CR13306","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1145\/333979.333984","volume":"47","author":"R Armoni","year":"2000","unstructured":"Armoni R, Ta-Shma A, Widgerson A, Zhou S (2000) An $$o(\\log (n)^{4\/3})$$ space algorithm for (s,\u2009t) connectivity in undirected graphs. J ACM 47(2):294\u2013311","journal-title":"J ACM"},{"key":"586_CR13307","first-page":"87","volume-title":"Constant-working-space algorithms for geometric problems","author":"T Asano","year":"2009","unstructured":"Asano T, Rote G (2009) Constant-working-space algorithms for geometric problems. In: CCCG, Vancouver, pp\u00a087\u201390"},{"issue":"8","key":"586_CR13308","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1016\/j.comgeo.2013.04.005","volume":"46","author":"T Asano","year":"2012","unstructured":"Asano T, Buchin K, Buchin M, Korman M, Mulzer W, Rote G, Schulz A (2012) Memory-constrained algorithms for simple polygons. Comput Geom Theory Appl 46(8):959\u2013969","journal-title":"Comput Geom Theory Appl"},{"issue":"9","key":"586_CR13309","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1016\/j.comgeo.2014.04.001","volume":"47","author":"L Barba","year":"2014","unstructured":"Barba L, Korman M, Langerman S, Silveira R (2014) Computing the visibility polygon using few variables. Comput Geom Theory Appl 47(9):918\u2013926","journal-title":"Comput Geom Theory Appl"},{"issue":"4","key":"586_CR13310","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1007\/s00453-014-9893-5","volume":"72","author":"L Barba","year":"2015","unstructured":"Barba L, Korman M, Langerman S, Sadakane K, Silveira R (2015) Space-time trade-offs for stack-based algorithms. Algorithmica 72(4):1097\u20131129","journal-title":"Algorithmica"},{"issue":"4","key":"586_CR13311","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum M, Floyd RW, Pratt VR, Rivest RL, Tarjan RE (1973) Time bounds for selection. J Comput Syst Sci 7(4):448\u2013461","journal-title":"J Comput Syst Sci"},{"key":"586_CR13312","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A Borodin","year":"1982","unstructured":"Borodin A, Cook S (1982) A time-space tradeoff for sorting on a general sequential model of computation. SIAM J Comput 11:287\u2013297","journal-title":"SIAM J Comput"},{"key":"586_CR13313","first-page":"1","volume":"6","author":"TM Chan","year":"2010","unstructured":"Chan TM (2010) Comparison-based time-space lower bounds for selection. ACM Trans Algorithms 6:1\u201316","journal-title":"ACM Trans Algorithms"},{"key":"586_CR13314","first-page":"147","volume-title":"Selection from read-only memory with limited workspace","author":"A Elmasry","year":"2013","unstructured":"Elmasry A, Juhl DD, Katajainen J, Satti SR (2013) Selection from read-only memory with limited workspace. In: COCOON, Hangzhou, pp\u00a0147\u2013157"},{"issue":"1","key":"586_CR13315","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(87)90002-X","volume":"34","author":"GN Frederickson","year":"1987","unstructured":"Frederickson GN (1987) Upper bounds for time-space trade-offs in sorting and selection. J Comput Syst Sci 34(1):19\u201326","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"586_CR13316","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","volume":"2","author":"R Jarvis","year":"1973","unstructured":"Jarvis R (1973) On the identification of the convex hull of a finite set of points in the plane. Inf Process Lett 2(1):18\u201321","journal-title":"Inf Process Lett"},{"key":"586_CR13317","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro JI, Paterson M (1980) Selection and sorting with limited storage. Theor Comput Sci 12:315\u2013323","journal-title":"Theor Comput Sci"},{"key":"586_CR13318","doi-asserted-by":"crossref","unstructured":"Nisan N, Szemeredi E, Wigderson A (1992) Undirected connectivity in o(log1.\u20095n) space. In: FOCS, Pittsburg, pp\u00a024\u201329","DOI":"10.1109\/SFCS.1992.267822"},{"key":"586_CR13319","first-page":"264","volume-title":"Optimal time-space trade-offs for sorting","author":"J Pagter","year":"1998","unstructured":"Pagter J, Rauhe T (1998) Optimal time-space trade-offs for sorting. In: FOCS, Palo Alto, pp\u00a0264\u2013268"},{"key":"586_CR13320","unstructured":"Pohl I (1969) A minimum storage algorithm for computing the median. IBM technical report RC2701"},{"key":"586_CR13321","doi-asserted-by":"crossref","unstructured":"Raman V, Ramnath S (1998) Improved upper bounds for time-space tradeoffs for selection with limited storage. In: SWAT \u201998, Stockholm, pp\u00a0131\u2013142","DOI":"10.1007\/BFb0054361"},{"issue":"4","key":"586_CR13322","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold O (2008) Undirected connectivity in log-space. J ACM 55(4):1\u201324","journal-title":"J ACM"},{"issue":"2","key":"586_CR13323","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch WJ (1970) Relationships between nondeterministic and deterministic tape complexities. J Comput Syst Sci 4(2):177\u2013192","journal-title":"J Comput Syst Sci"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_586","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:55:26Z","timestamp":1792108526000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_586"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_586","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}