{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:06:07Z","timestamp":1758272767816},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797081"},{"type":"electronic","value":"9783540797098"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79709-8_8","type":"book-chapter","created":{"date-parts":[[2008,5,13]],"date-time":"2008-05-13T10:33:17Z","timestamp":1210674797000},"page":"40-51","source":"Crossref","is-referenced-by-count":7,"title":["A Logspace Algorithm for Partial 2-Tree Canonization"],"prefix":"10.1007","author":[{"given":"Vikraman","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bireswar","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"K\u00f6bler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1007\/978-3-540-77120-3_71","volume-title":"Proc. 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: Proc. 18th International Symposium on Algorithms and Computation. LNCS, pp. 822\u2013833. Springer, Heidelberg (2007)"},{"key":"8_CR2","unstructured":"Allender, E.: Arithmetic circuits and counting complexity classes. In: Kraj\u00ed\u010dek, J. (ed.) Complexity of Computations and Proofs. Seconda Universita di Napoli. Quaderni di Matematica, vol.\u00a013, pp. 33\u201372 (2004)"},{"issue":"1","key":"8_CR3","first-page":"1","volume":"30","author":"E. Allender","year":"1996","unstructured":"Allender, E., Ogihara, M.: Relationships among PL, #L and the determinant. R.A.I.R.O. Informatique Th\u00e9orique et Applications\u00a030(1), 1\u201321 (1996)","journal-title":"R.A.I.R.O. Informatique Th\u00e9orique et Applications"},{"issue":"2","key":"8_CR4","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics\u00a023(2), 11\u201324 (1989)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"8_CR5","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/BF01994877","volume":"32","author":"S. Arnborg","year":"1992","unstructured":"Arnborg, S., Proskurowski, A.: Canonical representations of partial 2- and 3-trees. BIT\u00a032(2), 197\u2013214 (1992)","journal-title":"BIT"},{"issue":"3","key":"8_CR6","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1137\/0209047","volume":"9","author":"L. Babai","year":"1980","unstructured":"Babai, L., Erd\u0151s, P., Selkow, S.M.: Random graph isomorphism. SIAM Journal on Computing\u00a09(3), 628\u2013635 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Babai, L., Ku\u010dera, L.: Canonical labelling of graphs in linear average time. In: Proc. 20th IEEE Symposium on the Foundations of Computer Science, pp. 39\u201346 (1979)","DOI":"10.1109\/SFCS.1979.8"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Babai, L., Luks, E.: Canonical labeling of graphs. In: Proc. 15th ACM Symposium on Theory of Computing, pp. 171\u2013183 (1983)","DOI":"10.1145\/800061.808746"},{"key":"8_CR9","first-page":"115","volume":"63","author":"Y. Gurevich","year":"1997","unstructured":"Gurevich, Y.: From invariants to canonization. Bulletin of the European Association of Theoretical Computer Science (BEATCS)\u00a063, 115\u2013119 (1997)","journal-title":"Bulletin of the European Association of Theoretical Computer Science (BEATCS)"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/11786986_2","volume-title":"Automata, Languages and Programming","author":"M. Grohe","year":"2006","unstructured":"Grohe, M., Verbitsky, O.: Testing graph isomorphism in parallel by playing a game. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 3\u201314. Springer, Heidelberg (2006)"},{"key":"8_CR11","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":"8_CR12","first-page":"115","volume":"15","author":"F. Harary","year":"1968","unstructured":"Harary, F., Palmer, E.M.: On acyclic simplicial complexes. Mathematica\u00a015, 115\u2013122 (1968)","journal-title":"Mathematica"},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/3-540-45465-9_24","volume-title":"Automata, Languages and Programming","author":"A. Jakoby","year":"2002","unstructured":"Jakoby, A., Liskiewicz, M.: Paths Problems in Symmetric Logarithmic Space. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 269\u2013280. Springer, Heidelberg (2002)"},{"key":"8_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"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computation and Approximation","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computation and Approximation. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. In: Progress in Theoretical Computer Science. Birkh\u00e4user, Boston (1993)","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"8_CR17","first-page":"400","volume-title":"Proc. 24th ACM Symposium on Theory of Computing","author":"S. Lindell","year":"1992","unstructured":"Lindell, S.: A logspace algorithm for tree canonization. In: Proc. 24th ACM Symposium on Theory of Computing, pp. 400\u2013404. ACM Press, New York (1992)"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Luks, E.M.: Permutation groups and polynomial time computations. In: Finkelstein, L., Kantor, W.M. (eds.) Groups and Computation. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a011, pp. 139\u2013175. American Mathematical Society (1993)","DOI":"10.1090\/dimacs\/011\/11"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"key":"8_CR20","unstructured":"Thierauf, T., Wagner, F.: The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Technical Report TR07-068, Electronic Colloquium on Computational Complexity (ECCC) (2007)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79709-8_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:28:57Z","timestamp":1619508537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79709-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797081","9783540797098"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79709-8_8","relation":{},"subject":[]}}