ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > SEBASTIAN KUHNERT:
All reports by Author Sebastian Kuhnert:

TR09-053 | 20th May 2009
Johannes Köbler, Sebastian Kuhnert

The Isomorphism Problem for k-Trees is Complete for Logspace

We show that k-tree isomorphism can be decided in logarithmic space by giving a logspace canonical labeling algorithm. This improves over the previous StUL upper bound and matches the lower bound. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for k-trees are all complete for ... more >>>



ISSN 1433-8092 | Imprint