{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:28Z","timestamp":1759638328849},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_46","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"537-548","source":"Crossref","is-referenced-by-count":4,"title":["The Isomorphism Problem for k-Trees Is Complete for Logspace"],"prefix":"10.1007","author":[{"given":"Johannes","family":"K\u00f6bler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Kuhnert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"46_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/978-3-540-77120-3_71","volume-title":"Algorithms and Computation","author":"V. Arvind","year":"2007","unstructured":"Arvind, V., Das, B., K\u00f6bler, J.: The space complexity of k-tree isomorphism. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 822\u2013833. Springer, Heidelberg (2007)"},{"key":"46_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-540-79709-8_8","volume-title":"Computer Science \u2013 Theory and Applications","author":"V. Arvind","year":"2008","unstructured":"Arvind, V., Das, B., K\u00f6bler, J.: A logspace algorithm for partial 2-tree canonization. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 40\u201351. Springer, Heidelberg (2008)"},{"key":"46_CR3","volume-title":"The design and analysis of computer algorithms","author":"A. Aho","year":"1974","unstructured":"Aho, A., Hopcroft, J., Ullman, J.: The design and analysis of computer algorithms. Addison-Wesley, Reading (1974)"},{"issue":"1","key":"46_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. Theoretical Computer Science\u00a0107(1), 3\u201330 (1993)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"46_CR5","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1016\/j.ic.2006.02.002","volume":"204","author":"V. Arvind","year":"2006","unstructured":"Arvind, V., Kurur, P.P.: Graph isomorphism is in SPP. Information and Computation\u00a0204(5), 835\u2013852 (2006)","journal-title":"Information and Computation"},{"key":"46_CR6","doi-asserted-by":"crossref","unstructured":"Allender, E., Mahajan, M.: The complexity of planarity testing. Information and Computation\u00a0139(1) (February 2004)","DOI":"10.1016\/j.ic.2003.09.002"},{"key":"46_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01374526","volume":"25","author":"G. Buntrock","year":"1992","unstructured":"Buntrock, G., Damm, C., Hertrampf, U., Meinel, C.: Structure and importance of logspace-MOD classes. Mathematical Systems Theory\u00a025, 223\u2013237 (1992)","journal-title":"Mathematical Systems Theory"},{"key":"46_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Information and Control\u00a064, 2\u201322 (1985)","journal-title":"Information and Control"},{"key":"46_CR9","unstructured":"Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T., Wagner, F.: A log-space algorithm for canonization of planar graphs. CoRR (2008), http:\/\/arxiv.org\/abs\/0809.2319"},{"issue":"3","key":"46_CR10","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a054(3), 400\u2013411 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"46_CR11","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Randomness and Computation. Advances in Computing Research, vol.\u00a05, pp. 73\u201390. JAI Press (1989)"},{"issue":"1","key":"46_CR12","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s00453-001-0052-4","volume":"32","author":"J.G. Greco Del","year":"2002","unstructured":"Del Greco, J.G., Sekharan, C.N., Sridhar, R.: Fast parallel reordering and isomorphism testing of k-trees. Algorithmica\u00a032(1), 61\u201372 (2002)","journal-title":"Algorithmica"},{"key":"46_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-11493-9","volume-title":"Group-Theoretic Algorithms and Graph Isomorphism","author":"C.M. Hoffmann","year":"1982","unstructured":"Hoffmann, C.M.: Group-Theoretic Algorithms and Graph Isomorphism. LNCS, vol.\u00a0136. Springer, Heidelberg (1982)"},{"key":"46_CR14","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/S0022-0000(03)00042-4","volume":"66","author":"B. Jenner","year":"2003","unstructured":"Jenner, B., K\u00f6bler, J., McKenzie, P., Tor\u00e1n, J.: Completeness results for graph isomorphism. Journal of Computer and System Sciences\u00a066, 549\u2013566 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"46_CR15","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1137\/0603025","volume":"3","author":"M.M. Klawe","year":"1982","unstructured":"Klawe, M.M., Corneil, D.G., Proskurowski, A.: Isomorphism testing in hookup classes. SIAM Journal on Algebraic and Discrete Methods\u00a03(2), 260\u2013274 (1982)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"46_CR16","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science. Birkh\u00e4user, Boston (1993)","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"46_CR17","first-page":"400","volume-title":"Proceedings of the 24th STOC","author":"S. Lindell","year":"1992","unstructured":"Lindell, S.: A logspace algorithm for tree canonization. extended abstract. In: Proceedings of the 24th STOC, pp. 400\u2013404. ACM, New York (1992)"},{"key":"46_CR18","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1137\/0220070","volume":"20","author":"G. Miller","year":"1991","unstructured":"Miller, G., Reif, J.: Parallel tree contraction part 2: further applications. SIAM Journal on Computing\u00a020, 1128\u20131147 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"46_CR19","first-page":"376","volume-title":"Proceedings of the 37th STOC","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: Proceedings of the 37th STOC, pp. 376\u2013385. ACM, New York (2005)"},{"key":"46_CR20","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences\u00a037, 312\u2013323 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"46_CR21","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1137\/S009753970241096X","volume":"33","author":"J. Tor\u00e1n","year":"2004","unstructured":"Tor\u00e1n, J.: On the hardness of graph isomorphism. SIAM Journal on Computing\u00a033(5), 1093\u20131108 (2004)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T02:34:03Z","timestamp":1558492443000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}