Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs

Abstract

We give a deterministic logspace algorithm for the graph isomorphism problem for graphs with bounded tree-depth. We also show that the graph isomorphism problem is fixed parameter tractable for a related parameterized graph class where the graph parameter is the length of the longest cycle.