The Space Complexity of k-Tree Isomorphism
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
zuletzt geändert:
04.02.08
K
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Log in
Deutsch
English