{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T04:12:28Z","timestamp":1747714348901,"version":"3.40.5"},"publisher-location":"Cham","reference-count":9,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319156118"},{"type":"electronic","value":"9783319156125"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-15612-5_23","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T04:05:18Z","timestamp":1424664318000},"page":"258-269","source":"Crossref","is-referenced-by-count":1,"title":["Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs"],"prefix":"10.1007","author":[{"given":"Diptarka","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raghunath","family":"Tewari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci.\u00a04, 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Wigderson, A.: The complexity of graph connectivity. In: Mathematical Foundations of Computer Science, pp. 112\u2013132 (1992)","DOI":"10.1007\/3-540-55808-X_10"},{"key":"23_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 the Seventh Annual Structure in Complexity Theory Conference, pp. 27\u201333 (1992)","DOI":"10.1109\/SCT.1992.215378"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Imai, T., Nakagawa, K., Pavan, A., Vinodchandran, N.V., Watanabe, O.: An O(n1\/2\u2009+\u2009\u03b5)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. In: 2013 IEEE Conference on Computational Complexity (CCC), pp. 277\u2013286 (2013)","DOI":"10.1109\/CCC.2013.35"},{"key":"23_CR5","first-page":"35","volume":"21","author":"D. Chakraborty","year":"2014","unstructured":"Chakraborty, D., Pavan, A., Tewari, R., Vinodchandran, N.V., Yang, L.: New time-space upperbounds for directed reachability in high-genus and $h$-minor-free graphs. Electronic Colloquium on Computational Complexity (ECCC)\u00a021, 35 (2014)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"1","key":"23_CR6","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/2003685.2003687","volume":"3","author":"R. Kulkarni","year":"2011","unstructured":"Kulkarni, R.: On the power of isolation in planar graphs. TOCT\u00a03(1), 2 (2011)","journal-title":"TOCT"},{"issue":"4","key":"23_CR7","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1002\/net.3230140403","volume":"14","author":"A.S. LaPaugh","year":"1984","unstructured":"LaPaugh, A.S., Papadimitriou, C.H.: The even-path problem for graphs and digraphs. Networks\u00a014(4), 507\u2013513 (1984)","journal-title":"Networks"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1137\/S0097539797330343","volume":"29","author":"Z.P. Nedev","year":"1999","unstructured":"Nedev, Z.P.: Finding an Even Simple Path in a Directed Planar Graph. SIAM J. Comput.\u00a029, 685\u2013695 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"23_CR9","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J. Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with few crossings per edge. Combinatorica\u00a017(3), 427\u2013439 (1997)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15612-5_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T21:48:34Z","timestamp":1747691314000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-15612-5_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319156118","9783319156125"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15612-5_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}