{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T09:06:08Z","timestamp":1772874368037,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,9,30]],"date-time":"2017-09-30T00:00:00Z","timestamp":1506729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized by logarithmic-space (logspace) algorithms. This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous class of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.<\/jats:p>","DOI":"10.1145\/3132720","type":"journal-article","created":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T18:06:01Z","timestamp":1507140361000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Canonizing Graphs of Bounded Tree Width in Logspace"],"prefix":"10.1145","volume":"9","author":[{"given":"Michael","family":"Elberfeld","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1813695.1813706"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.04.002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90013-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM\u201915)","volume":"8973","author":"Das Bireswar"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.05.003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.16"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 29th Annual IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909) (Leibniz International Proceedings in Informatics)","volume":"4","author":"Datta Samir","year":"2009"},{"key":"e_1_2_1_10_1","volume-title":"Graduate Texts in Mathematics","volume":"173","author":"Diestel Reinhard","year":"2005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.21"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591865"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916) (Leibniz International Proceedings in Informatics)","volume":"47","author":"Elberfeld Michael","year":"2016"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804671"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335313"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371662"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 23rd Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Grohe Martin"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00042-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"e_1_2_1_22_1","first-page":"19","article-title":"Relativization of questions about log space computability","volume":"10","author":"Ladner Richard E.","year":"1976","journal-title":"Theory Comput. Syst."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90510-Z"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129750"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.28"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Daniel Lokshtanov Marcin Pilipczuk Micha\u0142 Pilipczuk and Saket Saurabh. 2014b. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded tree width. CoRR abs\/1404.0818 (2014).  Daniel Lokshtanov Marcin Pilipczuk Micha\u0142 Pilipczuk and Saket Saurabh. 2014b. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded tree width. CoRR abs\/1404.0818 (2014).","DOI":"10.1109\/FOCS.2014.28"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804670"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08404-6_32"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098279"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90010-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(71)90005-6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970241096X"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Heribert Vollmer. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer Berlin.   Heribert Vollmer. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer Berlin.","DOI":"10.1007\/978-3-662-03927-4"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 6th International Computer Science Symposium in Russia (CSR\u201911)","author":"Wagner Fabian","year":"2011"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3132720","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3132720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:10:56Z","timestamp":1750212656000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3132720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,30]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3132720"],"URL":"https:\/\/doi.org\/10.1145\/3132720","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,30]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}