{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:59Z","timestamp":1759638179082},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,5,7]],"date-time":"2013-05-07T00:00:00Z","timestamp":1367884800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,11]]},"DOI":"10.1007\/s00224-013-9469-9","type":"journal-article","created":{"date-parts":[[2013,5,5]],"date-time":"2013-05-05T22:52:10Z","timestamp":1367794330000},"page":"669-689","source":"Crossref","is-referenced-by-count":7,"title":["Log-Space Algorithms for Paths and Matchings in k-Trees"],"prefix":"10.1007","volume":"53","author":[{"given":"Bireswar","family":"Das","sequence":"first","affiliation":[]},{"given":"Samir","family":"Datta","sequence":"additional","affiliation":[]},{"given":"Prajakta","family":"Nimbhorkar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,5,7]]},"reference":[{"issue":"4","key":"9469_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/270563.270564","volume":"28","author":"E. Allender","year":"1997","unstructured":"Allender, E.: Making computation count: arithmetic circuits in the nineties. SIGACT News 28(4), 2\u201315 (1997)","journal-title":"SIGACT News"},{"issue":"4","key":"9469_CR2","doi-asserted-by":"crossref","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(4), 675\u2013723 (2009)","journal-title":"Theory Comput. Syst."},{"key":"9469_CR3","series-title":"Lecture Notes in Computer Science Series","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1007\/978-3-540-77120-3_71","volume-title":"Proceedings of ISAAC\u201907: The 18th International Symposium on Algorithms and Computation","author":"V. Arvind","year":"2007","unstructured":"Arvind, V., Das, B., K\u00f6bler, J.: The space complexity of k-tree isomorphism. In: Proceedings of ISAAC\u201907: The 18th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science Series, vol.\u00a04835, pp. 822\u2013833. Springer, Berlin (2007)"},{"issue":"1","key":"9469_CR4","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"M. Ben-Or","year":"1992","unstructured":"Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. SIAM J. Comput. 21(1), 54\u201358 (1992)","journal-title":"SIAM J. Comput."},{"key":"9469_CR5","series-title":"North-Holland Mathematics Studies Series","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-0208(08)73072-X","volume-title":"Topics in the Theory of Computation: Selected Papers of the International Conference on \u2018Foundations of Computation Theory\u2019, FCT\u201983","author":"B.V. Braunm\u00fchl","year":"1985","unstructured":"Braunm\u00fchl, B.V., Verbeek, R.: Input driven languages are recognized in logn space. In: Topics in the Theory of Computation: Selected Papers of the International Conference on \u2018Foundations of Computation Theory\u2019, FCT\u201983. North-Holland Mathematics Studies Series, vol.\u00a0102, pp. 1\u201319. North-Holland, Amsterdam (1985)"},{"key":"9469_CR6","first-page":"222","volume-title":"Proceedings of CCC\u201907: The 22nd Annual IEEE Conference on Computational Complexity","author":"M. Braverman","year":"2007","unstructured":"Braverman, M., Kulkarni, R., Roy, S.: Parity problems in planar graphs. In: Proceedings of CCC\u201907: The 22nd Annual IEEE Conference on Computational Complexity, pp. 222\u2013235 (2007)"},{"issue":"4","key":"9469_CR7","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"S. Buss","year":"1992","unstructured":"Buss, S., Cook, S., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM J. Comput. 21(4), 755\u2013780 (1992)","journal-title":"SIAM J. Comput."},{"key":"9469_CR8","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1109\/ICCI.1992.227709","volume-title":"Proceedings of ICCI\u201992: The 4th International IEEE Conference on Computing and Information","author":"N. Chandrasekharan","year":"1992","unstructured":"Chandrasekharan, N., Hannenhalli, S.: Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs. In: Proceedings of ICCI\u201992: The 4th International IEEE Conference on Computing and Information, pp. 42\u201345 (1992)"},{"key":"9469_CR9","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1051\/ita:2001119","volume":"35","author":"A. Chiu","year":"2001","unstructured":"Chiu, A., Davida, G., Litow, B.: Division in logspace-uniform NC1. RAIRO Theor. Inform. Appl. 35, 259\u2013275 (2001)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"9469_CR10","unstructured":"Datta, S., Roy, S.: A note on matching problems complete for logspace classes (2005, unpublished short)"},{"key":"9469_CR11","series-title":"Lecture Notes in Computer Science Series","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/978-3-540-74510-5_14","volume-title":"Proceedings of CSR\u201907: The 2nd International Symposium on Computer Science in Russia","author":"S. Datta","year":"2007","unstructured":"Datta, S., Kulkarni, R., Limaye, N., Mahajan, M.: Planarity, determinants, permanents, and (unique) matchings. In: Proceedings of CSR\u201907: The 2nd International Symposium on Computer Science in Russia. Lecture Notes in Computer Science Series, vol.\u00a04649, pp. 115\u2013126. Springer, Berlin (2007)"},{"key":"9469_CR12","doi-asserted-by":"crossref","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)","journal-title":"Theory Comput. Syst."},{"key":"9469_CR13","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1109\/FOCS.2010.21","volume-title":"Proceedings of FOCS\u201910: The 51st Annual IEEE Symposium on Foundations of Computer Science","author":"M. Elberfeld","year":"2010","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: Proceedings of FOCS\u201910: The 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 143\u2013152 (2010)"},{"issue":"3","key":"9469_CR14","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jcss.1997.1485","volume":"54","author":"K. Etessami","year":"1997","unstructured":"Etessami, K.: Counting quantifiers, successor relations, and logarithmic space. J. Comput. Syst. Sci. 54(3), 400\u2013411 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9469_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/978-3-540-77120-3_13","volume-title":"Proceedings of ISAAC\u201907: The 18th International Symposium on Algorithms and Computation","author":"U. Flarup","year":"2007","unstructured":"Flarup, U., Koiran, P., Lyaudet, L.: On the expressive power of planar perfect matching and permanents of bounded treewidth matrices. In: Proceedings of ISAAC\u201907: The 18th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, pp. 124\u2013136. Springer, Berlin (2007)"},{"issue":"1","key":"9469_CR16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s00453-001-0052-4","volume":"32","author":"J.G.D. Greco","year":"2002","unstructured":"Greco, J.G.D., Chandrasekharan, N., Sridhar, R.: Fast parallel reordering and isomorphism testing of k-trees. Algorithmica 32(1), 61\u201372 (2002)","journal-title":"Algorithmica"},{"issue":"2","key":"9469_CR17","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1016\/j.dam.2002.12.005","volume":"145","author":"A. Gupta","year":"2005","unstructured":"Gupta, A., Nishimura, N., Proskurowski, A., Ragde, P.: Embeddings of k-connected graphs of pathwidth\u00a0k. Discrete Appl. Math. 145(2), 242\u2013265 (2005)","journal-title":"Discrete Appl. Math."},{"key":"9469_CR18","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1112\/S002557930000245X","volume":"15","author":"F. Harary","year":"1968","unstructured":"Harary, F., Palmer, E.M.: On acyclic simplicial complexes. Mathematika 15, 115\u2013122 (1968)","journal-title":"Mathematika"},{"issue":"4","key":"9469_CR19","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W. Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65(4), 695\u2013716 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9469_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/11786986_40","volume-title":"Proceedings of ICALP\u201906: The 33rd International Colloquium on Automata, Languages and Programming","author":"T.M. Hoang","year":"2006","unstructured":"Hoang, T.M., Mahajan, M., Thierauf, T.: On the bipartite unique perfect matching problem. In: Proceedings of ICALP\u201906: The 33rd International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, pp. 453\u2013464. Springer, Berlin (2006)"},{"key":"9469_CR21","series-title":"Lecture Notes in Computer Science Series","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/978-3-540-77050-3_18","volume-title":"Proceedings of FSTTCS\u201907: The 27th Annual Conference on Foundations of Software Technology and Theoretical Computer Science","author":"A. Jakoby","year":"2007","unstructured":"Jakoby, A., Tantau, T.: Logspace algorithms for computing shortest and longest paths in series-parallel graphs. In: Proceedings of FSTTCS\u201907: The 27th Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science Series, vol.\u00a04855, pp. 216\u2013227. Springer, Berlin (2007)"},{"issue":"1","key":"9469_CR22","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R.M. Karp","year":"1986","unstructured":"Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica 6(1), 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"9469_CR23","series-title":"Lecture Notes in Computer Science Series","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/978-3-642-03816-7_46","volume-title":"Proceedings of MFCS\u201909: The 34th International Symposium on Mathematical Foundations of Computer Science","author":"J. K\u00f6bler","year":"2009","unstructured":"K\u00f6bler, J., Kuhnert, S.: The isomorphism problem for k-trees is complete for logspace. In: Proceedings of MFCS\u201909: The 34th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science Series, vol.\u00a05734, pp. 537\u2013548. Springer, Berlin (2009)"},{"issue":"8","key":"9469_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.2010.008","volume":"2010","author":"N. Limaye","year":"2010","unstructured":"Limaye, N., Mahajan, M., Nimbhorkar, P.: Longest paths in planar DAGs in unambiguous log-space. Chic. J. Theor. Comput. Sci. 2010(8), 1\u201316 (2010). CATS 2009 special issue","journal-title":"Chic. J. Theor. Comput. Sci."},{"issue":"3","key":"9469_CR25","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/s00224-009-9233-3","volume":"46","author":"N. Limaye","year":"2010","unstructured":"Limaye, N., Mahajan, M., Rao, B.V.R.: Arithmetizing classes around NC1 and L. Theory Comput. Syst. 46(3), 499\u2013522 (2010). Special issue for STACS 2007","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9469_CR26","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"4","key":"9469_CR27","doi-asserted-by":"crossref","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O. Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17 (2008)","journal-title":"J. ACM"},{"issue":"4","key":"9469_CR28","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9469_CR29","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory, Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9469_CR30","series-title":"Lecture Notes in Computer Science Series","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/978-3-642-03409-1_29","volume-title":"Proceedings of FCS\u201909: The 17th International Symposium on Fundamentals of Computation Theory","author":"T. Thierauf","year":"2009","unstructured":"Thierauf, T., Wagner, F.: Reachability in K 3,3-free graphs and K 5-free graphs is in unambiguous log-space. In: Proceedings of FCS\u201909: The 17th International Symposium on Fundamentals of Computation Theory. Lecture Notes in Computer Science Series, vol.\u00a05699, pp.\u00a0323\u2013334. Springer, Berlin (2009)"},{"issue":"3","key":"9469_CR31","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1006\/jagm.1994.1022","volume":"16","author":"E. Wanke","year":"1994","unstructured":"Wanke, E.: Bounded tree-width and LOGCFL. J. Algorithms 16(3), 470\u2013491 (1994)","journal-title":"J. Algorithms"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9469-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/article\/10.1007\/s00224-013-9469-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9469-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:25Z","timestamp":1558684465000},"score":1,"resource":{"primary":{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/10.1007\/s00224-013-9469-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,7]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["9469"],"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/s00224-013-9469-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,7]]}}}