Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

The Space Complexity of k-Tree Isomorphism

V. Arvind, B. Das, J. Köbler


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