{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:54Z","timestamp":1760202714486,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319670881"},{"type":"electronic","value":"9783319670898"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","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":[[2017]]},"DOI":"10.1007\/978-3-319-67089-8_13","type":"book-chapter","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T08:47:26Z","timestamp":1503564446000},"page":"176-191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Parameterized Graph Connectivity and Polynomial-Time Sub-Linear-Space Short Reductions"],"prefix":"10.1007","author":[{"given":"Tomoyuki","family":"Yamakami","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,25]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/s00224-009-9172-z","volume":"45","author":"E Allender","year":"2009","unstructured":"Allender, E., Barrington, D.A.M., Chakraborty, T., Datta, S., Roy, S.: Planar and grid graph reachability problems. Theory Comput. Syst. 45, 675\u2013723 (2009)","journal-title":"Theory Comput. Syst."},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.ic.2003.09.002","volume":"189","author":"E Allender","year":"2004","unstructured":"Allender, E., Mahajan, M.: The complexity of planarity testing. Inf. Comput. 189, 117\u2013134 (2004)","journal-title":"Inf. Comput."},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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.: \n                    \n                      \n                    \n                    $$\\widetilde{O}(\\sqrt{n})$$\n                  -space and polynomial-time algorithm for planar directed graph reachability. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014. LNCS, vol. 8635, pp. 45\u201356. Springer, Heidelberg (2014). doi:\n                    10.1007\/978-3-662-44465-8_5"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1137\/S0097539793283151","volume":"27","author":"G Barnes","year":"1998","unstructured":"Barnes, G., Buss, J.F., Ruzzo, W.L., Schieber, B.: A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J. Comput. 27, 1273\u20131282 (1998)","journal-title":"SIAM J. Comput."},{"key":"13_CR5","unstructured":"Bourke, C., Tewari, R., Vinodchandran, N.V.: Directed planar reachability is in unambiguous logspace. In: Proceedings CCC 2007, 217\u2013221 (2007)"},{"key":"13_CR6","unstructured":"Chakraborty, D., Pavan, A., Tewari, R., Vinodchandran, N.V., Yang, L.F.: New time-space upperbounds for directed reachability in high-genus and H-minor-free graphs. In: The Proceedings of FSTTCS 2014, Leibniz International Proceedings in Informatics, pp. 585\u2013595 (2014)"},{"key":"13_CR7","volume-title":"Handbook of Graph Theory","author":"JL Gross","year":"2014","unstructured":"Gross, J.L., Yellen, J., Zhang, P.: Handbook of Graph Theory. CRC Press, Boca Raton (2014)"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complement. SIAM J. Comput. 17, 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"ND Jones","year":"1975","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11, 68\u201375 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR10","unstructured":"Kannan, S., Khanna, S., Roy, S.: STCON in directed unique-path graphs. In: Proceedings of FSTTCS 2008, UPIcs 2, pp. 256\u2013267 (2008)"},{"key":"13_CR11","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, 1\u201324 (2008)","journal-title":"J. ACM"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.P.: Pseudorandom walks on regular digraphs and the RL vs. L problem. In: The Proceedings of STOC 2006, pp. 457\u2013466 (2006)","DOI":"10.1145\/1132516.1132583"},{"key":"13_CR13","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, 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Inf. 26, 279\u2013284 (1988)","journal-title":"Acta Inf."},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00224-007-2011-1","volume":"41","author":"T Tantau","year":"2007","unstructured":"Tantau, T.: Logspace optimization problems and their approximation properties. Theory Comput. Syst. 41, 327\u2013350 (2007)","journal-title":"Theory Comput. Syst."},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-319-03780-6_28","volume-title":"Combinatorial Optimization and Applications","author":"T Yamakami","year":"2013","unstructured":"Yamakami, T.: Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 318\u2013329. Springer, Cham (2013). doi:\n                    10.1007\/978-3-319-03780-6_28\n                    \n                  . A complete version is available at \n                    arXiv:1601.01118v1"},{"key":"13_CR17","unstructured":"Yamakami, T.: The 2CNF Boolean formula satisfiability problem and the linear space hypothesis. In: The Proceedings of MFCS 2017, 7\u201311 August 2017. Leibniz International Proceedings in Informatics (2017, to appear)"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67089-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T10:00:33Z","timestamp":1578477633000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67089-8_13"}},"subtitle":["(Preliminary Report)"],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319670881","9783319670898"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67089-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"25 August 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Reachability Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"London","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 September 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/rp17.cs.rhul.ac.uk\/past_rps.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}