Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

Bireswar Das, Jacobo Toran, Fabian Wagner

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time [Bod90],[YBFT99]. We give restric…