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 \cite{Bo90},\cite{YBFT}.

We give restricted space algorithms for these problems proving the following results:

Isomorphism for bounded tree distance width graphs is in L and thus complete ... more >>>

Oded Goldreich

We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs.

We essentially determine the query complexity of these testing problems in the special case of ...
more >>>

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The graph isomorphism distance between two graphs $G_u$ and $G_k$ is the fraction of entries in the adjacency matrix that has to be changed to make $G_u$ isomorphic to $G_k$. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in ... more >>>