Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GRAPH ISOMOPHISM:
Reports tagged with Graph Isomophism:
TR09-094 | 7th October 2009
Bireswar Das, Jacobo Toran, Fabian Wagner

Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

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 >>>


TR19-102 | 10th August 2019
Oded Goldreich

Testing Isomorphism in the Bounded-Degree Graph Model

Revisions: 1

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 >>>




ISSN 1433-8092 | Imprint