Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

TR20-135 | 9th September 2020
Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

Estimation of Graph Isomorphism Distance in the Query World

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

ISSN 1433-8092 | Imprint