Details

Autor(en) / Beteiligte

• Köbler, Johannes
• Kuhnert, Sebastian

Titel

The Isomorphism Problem for k-Trees Is Complete for Logspace

Ist Teil von

• Mathematical Foundations of Computer Science 2009, p.537-548

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 deterministic logspace. We also show that even simple structural properties of k-trees are complete for logspace.