*BibTeX*

@Article{ADKK12ktree-canonization, author = {V. Arvind and Bireswar Das and Johannes Köbler and Sebastian Kuhnert}, title = {The isomorphism problem for $k$-trees is complete for logspace}, journal = {Information and Computation}, year = 2012, volume = 217, month = 8, pages = {1-11}, issn = {0890-5401}, doi = {10.1016/j.ic.2012.04.002}, }

**The isomorphism problem for
k-trees is complete for logspace.**

With V. Arvind, Bireswar Das, Johannes Köbler.

*Information and Computation*217:1–11 (Aug. 2012)

Abstract.We show that, forkconstant,k-tree isomorphism can be decided in logarithmic space by giving anO(nlogn) 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 Lindellʼs tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem fork-trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties ofk-trees. We also show that a variant of our canonical labeling algorithm runs in timeO((k+1)!logn), wherenis the number of vertices, yielding the fastest known FPT algorithm fork-tree isomorphism.

*BibTeX*

@InProceedings{KK09ktree-canonization, author = {Johannes Köbler and Sebastian Kuhnert}, title = {The isomorphism problem for $k$-trees is complete for logspace}, booktitle = {Mathematical Foundations of Computer Science 2009. 34th International Symposium (MFCS)}, year = 2009, series = {LNCS}, number = 5734, publisher = {Springer}, address = {Berlin}, isbn = {978-3-642-03815-0}, doi = {10.1007/978-3-642-03816-7_46}, pages = {537-548}, }

Conference version:

**The isomorphism problem for k-Trees is complete
for logspace**

With Johannes Köbler.

*Mathematical Foundations of Computer Science*(Proceedings of 34th MFCS). Springer, 2009. Pp. 537–548.