{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:58:59Z","timestamp":1780783139193,"version":"3.54.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_14","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:13:59Z","timestamp":1780780439000},"page":"190-203","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reachability in\u00a0Graphs with\u00a0Polynomially Many Surface Non-separating Cycles is in\u00a0UL"],"prefix":"10.1007","author":[{"given":"Neelabjo Shubhashis","family":"Choudhury","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chetan","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghunath","family":"Tewari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"key":"14_CR1","doi-asserted-by":"publisher","unstructured":"Gupta, C., Sharma, V.R., Tewari, R.: Reachability in o (log n) genus graphs is in unambiguous logspace. In: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pp. 34:1\u201334:13 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.34","DOI":"10.4230\/LIPIcs.STACS.2019.34"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/3-540-54458-5_61","volume-title":"Fundamentals of Computation Theory","author":"G Buntrock","year":"1991","unstructured":"Buntrock, G., Jenner, B., Lange, K.-J., Rossmanith, P.: Unambiguity and fewness for logarithmic space. In: Budach, L. (ed.) FCT 1991. LNCS, vol. 529, pp. 168\u2013179. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/3-540-54458-5_61"},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1006\/jcss.1999.1646","volume":"59","author":"E Allender","year":"1999","unstructured":"Allender, E., Reinhardt, K., Zhou, S.: Isolation, matching, and counting: uniform and nonuniform upper bounds. J. Comput. Syst. Sci. 59, 164\u2013181 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C \u00c0lvarez","year":"1993","unstructured":"\u00c0lvarez, C., Jenner, B.: A very hard log-space counting class. Theoret. Comput. Sci. 107, 3\u201330 (1993)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"14_CR5","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). https:\/\/doi.org\/10.1145\/1391289.1391291","journal-title":"J. ACM"},{"issue":"3","key":"14_CR6","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with 0(1) worst case access time. J. ACM 31(3), 538\u2013544 (1984). https:\/\/doi.org\/10.1145\/828.1884","journal-title":"J. ACM"},{"issue":"4","key":"14_CR7","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1137\/S0097539798339041","volume":"29","author":"K Reinhardt","year":"2000","unstructured":"Reinhardt, K., Allender, E.: Making nondeterminism unambiguous. SIAM J. Comput. 29(4), 1118\u20131131 (2000). https:\/\/doi.org\/10.1137\/S0097539798339041","journal-title":"SIAM J. Comput."},{"key":"14_CR8","doi-asserted-by":"publisher","unstructured":"Kallampally, V.A.T., Tewari, R.: Trading determinism for time in space bounded computations. In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22\u201326, 2016 - Krak\u00f3w, Poland, pp. 10:1\u201310:13 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.10","DOI":"10.4230\/LIPIcs.MFCS.2016.10"},{"key":"14_CR9","doi-asserted-by":"publisher","unstructured":"van Melkebeek, D., Prakriya, G.: Derandomizing isolation in space-bounded settings. In: 32nd Computational Complexity Conference, CCC 2017, July 6\u20139, 2017, Riga, Latvia, pp. 5:1\u20135:32 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2017.5","DOI":"10.4230\/LIPIcs.CCC.2017.5"},{"issue":"4","key":"14_CR10","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/s00037-012-0047-3","volume":"21","author":"A Pavan","year":"2012","unstructured":"Pavan, A., Tewari, R., Vinodchandran, N.V.: On the power of unambiguity in log-space. Comput. Complex. 21(4), 643\u2013670 (2012). https:\/\/doi.org\/10.1007\/s00037-012-0047-3","journal-title":"Comput. Complex."},{"issue":"4","key":"14_CR11","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., Chakraborty, T., Datta, S., Roy, S.: Planar and grid graph reachability problems. Theory Comput. Syst. 45(4), 675\u2013723 (2009). https:\/\/doi.org\/10.1007\/s00224-009-9172-z","journal-title":"Theory Comput. Syst."},{"key":"14_CR12","doi-asserted-by":"publisher","unstructured":"Thierauf, T., Wagner, F.: Reachability in $$K_{3,3}$$-free graphs and $$K_5$$-free graphs is in unambiguous log-space. In: 17th International Conference on Foundations of Computation Theory (FCT), Lecture Notes in Computer Science 5699, pp. 323\u2013334. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03409-1_29","DOI":"10.1007\/978-3-642-03409-1_29"},{"issue":"1","key":"14_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1490270.1490274","volume":"1","author":"C Bourke","year":"2009","unstructured":"Bourke, C., Tewari, R., Vinodchandran, N.V.: Directed planar reachability is in unambiguous log-space. ACM Trans. Comput. Theory 1(1), 1\u201317 (2009). https:\/\/doi.org\/10.1145\/1490270.1490274","journal-title":"ACM Trans. Comput. Theory"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2012.03.002","volume":"215","author":"R Tewari","year":"2012","unstructured":"Tewari, R., Vinodchandran, N.V.: Green\u2019s theorem and isolation in planar graphs. Inf. Comput. 215, 1\u20137 (2012). https:\/\/doi.org\/10.1016\/j.ic.2012.03.002","journal-title":"Inf. Comput."},{"issue":"3","key":"14_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1714450.1714451","volume":"1","author":"J Kyncl","year":"2010","unstructured":"Kyncl, J., Vyskocil, T.: Logspace reduction of directed reachability for bounded genus graphs to the planar case. ACM Trans. Comput. Theory 1(3), 1\u201311 (2010). https:\/\/doi.org\/10.1145\/1714450.1714451","journal-title":"ACM Trans. Comput. Theory"},{"issue":"3","key":"14_CR16","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/j.jcss.2011.11.002","volume":"78","author":"S Datta","year":"2012","unstructured":"Datta, S., Kulkarni, R., Tewari, R., Vinodchandran, N.V.: Space complexity of perfect matching in bounded genus bipartite graphs. J. Comput. Syst. Sci. 78(3), 765\u2013779 (2012). https:\/\/doi.org\/10.1016\/j.jcss.2011.11.002","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR17","doi-asserted-by":"publisher","unstructured":"Datta, S., Gupta, C., Jain, R., Mukherjee, A., Sharma, V.R., Tewari, R.: Reachability and matching in single crossing minor free graphs. In: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 16:1\u201316:16, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2021.16","DOI":"10.4230\/LIPIcs.FSTTCS.2021.16"},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s00224-009-9204-8","volume":"47","author":"S Datta","year":"2010","unstructured":"Datta, S., Kulkarni, R., Roy, S.: Deterministically isolating a perfect matching in bipartite planar graphs. Theory Comput. Syst. 47, 737\u2013757 (2010). https:\/\/doi.org\/10.1007\/s00224-009-9204-8","journal-title":"Theory Comput. Syst."},{"key":"14_CR19","unstructured":"Datta, S., Kumar, P., Mukherjee, A., Tawari, A., Vortmeier, N., Zeume, T.: Dynamic complexity of reachability: how many changes can we handle? In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8\u201311, 2020, Saarbr\u00fccken, Germany (Virtual Conference), pp. 122:1\u2013122:19 (2020)"},{"key":"14_CR20","doi-asserted-by":"publisher","unstructured":"Das, B., Datta, S., Nimbhorkar, P.: Log-space algorithms for paths and matchings in k-trees. In: 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 215\u2013226, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2010). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2010.2456","DOI":"10.4230\/LIPIcs.STACS.2010.2456"},{"key":"14_CR21","doi-asserted-by":"publisher","unstructured":"Mahajan, M., Varadarajan, K.R.: A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC \u201900). Association for Computing Machinery, New York, NY, USA, pp. 351\u2013357 (2000). https:\/\/doi.org\/10.1145\/335305.335346","DOI":"10.1145\/335305.335346"},{"key":"14_CR22","doi-asserted-by":"publisher","unstructured":"Gupta, C., Sharma, V.R., Tewari, R.: Efficient isolation of perfect matching in o(log n) genus bipartite graphs. In: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 170, pp. 43:1\u201343:13, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.43","DOI":"10.4230\/LIPIcs.MFCS.2020.43"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Paths, trees and flowers. Can. J. Math. 449\u2013467 (1965)","DOI":"10.4153\/CJM-1965-045-4"},{"key":"14_CR24","unstructured":"Lov\u00e1sz, L.: On determinants, matchings, and random algorithms. In: FCT, pp. 565\u2013574 (1979)"},{"key":"14_CR25","unstructured":"Arora, R., Gupta, A., Gurjar, R., Tewari, R.: Derandomizing isolation lemma for $$k_{3,3}$$-free and $$k_5$$-free bipartite graphs. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17\u201320, 2016, Orl\u00e9ans, France, pp. 10:1\u201310:15 (2016)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27732-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:01Z","timestamp":1780780441000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}