The Space Complexity of k-Tree Isomorphism
V. Arvind, B. Das, J. Köbler
Abstract:
We show that isomorphism testing of k-trees is in the class StUL (strongly unambiguous logspace). This bound follows from a deterministic logspace algorithm that accesses a strongly unambiguous logspace oracle for canonizing k-trees. Further we give a logspace canonization algorithm for k-paths.
PDF: ktree.pdf