{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T04:15:29Z","timestamp":1748751329193,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662491911"},{"type":"electronic","value":"9783662491928"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49192-8_2","type":"book-chapter","created":{"date-parts":[[2016,1,7]],"date-time":"2016-01-07T15:47:27Z","timestamp":1452181647000},"page":"17-28","source":"Crossref","is-referenced-by-count":0,"title":["Relating Sublinear Space Computability Among Graph Connectivity and Related Problems"],"prefix":"10.1007","author":[{"given":"Tatsuya","family":"Imai","sequence":"first","affiliation":[]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,8]]},"reference":[{"key":"2_CR1","unstructured":"Asano, T., Doerr, B.: Memory-constrained algorithms for shortest path problem. In: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011) (2011)"},{"key":"2_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-3-662-44465-8_5","volume-title":"Mathematical Foundations of Computer Science 2014","author":"T Asano","year":"2014","unstructured":"Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O.: $$\\tilde{O}(\\sqrt{n})$$ -space and polynomial-time algorithm for planar directed graph reachability. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 45\u201356. Springer, Heidelberg (2014)"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Barnes, G., Buss, J.F., Ruzzo, W.L., Schieber, B.: A sublinear space, polynomial time algorithm for directed s-t connectivity. In: Proceedings of Structure in Complexity Theory Conference, pp. 27\u201333. IEEE Computer Society Press (1992)","DOI":"10.1109\/SCT.1992.215378"},{"key":"2_CR4","unstructured":"Chakraborty, D., Pavan, A., Tewari, R., Vinodchandran, V., Yang, L.: New time-space upper bounds for directed reachability in high-genus and $$H$$ -minor-free graphs. In: ECCC TR14-035 (2014)"},{"key":"2_CR5","unstructured":"Imai, T.: Polynomial time memory constrained shortest path algorithms for directed graphs (in Japanese). In Proceedings of 12th Forum for Informatics (FIT 2013), IEICE Japan, RA-002 (2013)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Imai, T., Nakagawa, K., Pavan, A., Vinodchandran, N.V., Watanabe, O.: An $$O({n^{{1\\over 2}+\\epsilon }})$$ -space and polynomial-time algorithm for directed planar reachability. In: Proceedings of the 28th Conference on Computational Complexity (CCC 2013), pp. 277\u2013286. IEEE (2013)","DOI":"10.1109\/CCC.2013.35"},{"issue":"4","key":"2_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 1\u201324 (2008)","journal-title":"J. ACM"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/3-540-55808-X_10","volume-title":"Mathematical Foundations of Computer Science 1992","author":"A Wigderson","year":"1992","unstructured":"Wigderson, A.: The complexity of graph connectivity. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 112\u2013132. Springer, Heidelberg (1992)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2016: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49192-8_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T02:19:15Z","timestamp":1748744355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49192-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662491911","9783662491928"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49192-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}