Arvind, V.V.ArvindDas, BireswarBireswarDasKöbler, JohannesJohannesKöblerKuhnert, SebastianSebastianKuhnert2025-08-302025-08-302012-08-0110.1016/j.ic.2012.04.0022-s2.0-84860323774http://repository.iitgn.ac.in/handle/IITG2025/21041We show that, for k constant, k-tree isomorphism can be decided in logarithmic space by giving an O(klogn) space canonical labeling algorithm. The algorithm computes a unique tree decomposition, uses colors to fully encode the structure of the original graph in the decomposition tree and invokes Lindells tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for k-trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties of k-trees. We also show that a variant of our canonical labeling algorithm runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. © 2012 Elsevier Inc. All rights reserved.trueGraph canonization | Graph isomorphism | k-Trees | Logspace completeness | Space complexityArticle109026511-11August 201210arJournal6WOS:000306724000001