Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼
 

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

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