Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style
icon Submit Paper


RSS-Feed
REPORTS > KEYWORD > GRAPH ISOMORPHISM, LOG-SPACE:
Reports tagged with Graph Isomorphism, Log-space:
TR10-050 | 25th March 2010
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Graph Isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space

Graph isomorphism is an important and widely studied computational problem, with
a yet unsettled complexity.
However, the exact complexity is known for isomorphism of various classes of
graphs. Recently [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.
We extend this result of [DLN$^+$09] further
to the ... more >>>



ISSN 1433-8092 | Imprint