{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:47:44Z","timestamp":1725497264469},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_71","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T06:31:09Z","timestamp":1196922669000},"page":"822-833","source":"Crossref","is-referenced-by-count":6,"title":["The Space Complexity of k-Tree Isomorphism"],"prefix":"10.1007","author":[{"given":"V.","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":"71_CR1","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s002240000102","volume":"31","author":"E. Allender","year":"1989","unstructured":"Allender, E., Lange, K.-J.: RUSPACE(log n) is contained in DSPACE(log2 n\/loglog n). Theory of Computing Systems\u00a031, 539\u2013550 (1989)","journal-title":"Theory of Computing Systems"},{"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)","key":"71_CR2"},{"issue":"1","key":"71_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":"71_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"},{"key":"71_CR5","first-page":"303","volume-title":"Proc. 27th IEEE Symposium on the Foundations of Computer Science","author":"L. Babai","year":"1986","unstructured":"Babai, L.: A Las Vegas-NC algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues. In: Proc. 27th IEEE Symposium on the Foundations of Computer Science, pp. 303\u2013312. IEEE Computer Society Press, Los Alamitos (1986)"},{"key":"71_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.\u00a0529, pp. 168\u2013179. Springer, Heidelberg (1991)"},{"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)","key":"71_CR7","DOI":"10.1145\/800061.808746"},{"key":"71_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Automata, Languages and Programming","author":"H. Bodlaender","year":"1988","unstructured":"Bodlaender, H.: Dynamic programming on graphs with bounded treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) Automata, Languages and Programming. LNCS, vol.\u00a0317, pp. 105\u2013118. Springer, Heidelberg (1988)"},{"issue":"4","key":"71_CR9","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H. Bodlaender","year":"1990","unstructured":"Bodlaender, H.: Polynomial algorithm for graph isomorphism and chromatic index on partial k-trees. Journal of Algorithms\u00a011(4), 631\u2013643 (1990)","journal-title":"Journal of Algorithms"},{"key":"71_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/3-540-63385-5_30","volume-title":"Computational Logic and Proof Theory","author":"S. Buss","year":"1997","unstructured":"Buss, S.: Alogtime algorithms for tree isomorphism, comparison, and canonization. In: Gottlob, G., Leitsch, A., Mundici, D. (eds.) KGC 1997. LNCS, vol.\u00a01289, pp. 18\u201333. Springer, Heidelberg (1997)"},{"issue":"6","key":"71_CR11","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0020-0190(90)90011-L","volume":"34","author":"N. Chandrasekharan","year":"1990","unstructured":"Chandrasekharan, N.: Isomorphism testing of k-trees is in NC. Information Processing Letters\u00a034(6), 283\u2013287 (1990)","journal-title":"Information Processing Letters"},{"issue":"10","key":"71_CR12","doi-asserted-by":"publisher","first-page":"1178","DOI":"10.1109\/12.5979","volume":"37","author":"N. Chandrasekharan","year":"1988","unstructured":"Chandrasekharan, N., Iyengar, S.S.: NC algorithms for recognizing chordal graphs and k trees. IEEE Transactions on Computers\u00a037(10), 1178\u20131183 (1988)","journal-title":"IEEE Transactions on Computers"},{"key":"71_CR13","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"1997","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol.\u00a0173. Springer, Heidelberg (1997)"},{"issue":"2","key":"71_CR14","doi-asserted-by":"publisher","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 k. Discrete Applied Mathematics\u00a0145(2), 242\u2013265 (2005)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"71_CR15","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":"71_CR16","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":"71_CR17","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":"71_CR18","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":"71_CR19","doi-asserted-by":"crossref","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 of Algebraic Discrete Methods\u00a03(2), 260\u2013274 (1982)","journal-title":"SIAM Journal of Algebraic Discrete Methods"},{"key":"71_CR20","series-title":"Lecture Notes in Computer Science","volume-title":"Treewidth","year":"1994","unstructured":"Kloks, T. (ed.): Treewidth. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"71_CR21","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":"71_CR22","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E. Luks","year":"1982","unstructured":"Luks, E.: Isomorphism of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences\u00a025, 42\u201365 (1982)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\/2","key":"71_CR23","first-page":"1","volume":"56","author":"G.L. Miller","year":"1983","unstructured":"Miller, G.L.: Isomorphism of k-contractible graphs. Information and Computation\u00a056(1\/2), 1\u201320 (1983)","journal-title":"Information and Computation"},{"unstructured":"Proskurowski, A.: Maximal graphs of path-width k or searching a partial k-caterpillar. Technical Report UO-CIS-TR-89-17, University of Oregon (1989)","key":"71_CR24"},{"key":"71_CR25","first-page":"576","volume-title":"Proc. 28th ACM Symposium on Theory of Computing","author":"D.A. Spielman","year":"1996","unstructured":"Spielman, D.A.: Faster isomorphism testing of strongly regular graphs. In: Proc. 28th ACM Symposium on Theory of Computing, pp. 576\u2013584. ACM Press, New York (1996)"},{"key":"71_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/3-540-51517-8_142","volume-title":"EUROCAL 1987","author":"P. Scheffler","year":"1989","unstructured":"Scheffler, P., Seese, D.: A combinatorial and logical approach to linear-time computability. In: Davenport, J.H. (ed.) ISSAC 1987 and EUROCAL 1987. LNCS, vol.\u00a0378, pp. 379\u2013380. Springer, Heidelberg (1989)"},{"issue":"3","key":"71_CR27","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1006\/jagm.1994.1022","volume":"16","author":"E. Wanke","year":"1994","unstructured":"Wanke, E.: Bounded tree-width and LOGCFL. Journal of Algorithms\u00a016(3), 470\u2013491 (1994)","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_71.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:01:26Z","timestamp":1619506886000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_71","relation":{},"subject":[]}}