<p>What algorithms are known for the graph isomorphism problem? Can those algorithms be related to algorithms for other graph theoretical problems (e.g. subgraph problem, counting graph isomorphisms)?</p>

CC BY-SA 3.0
2014-12-12T16:21:28.007Z
Your question seems too broad. BTW the fastest known algorithm runs in $e^{O(\sqrt(n \log n))}$ (Babai et al, 1983); there are a bunch of well known softwares for GI that use some (advanced) techniques to prune the search tree: nauty, saucy, bliss, traces, conauto. For an up-to-date comparison/bibliography see [Practical graph isomorphism, II](http://arxiv.org/abs/1301.1493).
Marzio De Biasi
CC BY-SA 3.0
2014-12-12T18:31:43.237Z
I think the question is fine, and would be very interested to see a survey answer along the lines of this one: http://cstheory.stackexchange.com/questions/9241/approximation-algorithms-for-metric-tsp/11557#11557 McKay's survey seems more focused on implementation issues, and less on algorithms per say.
Huck Bennett
CC BY-SA 3.0
2014-12-13T04:25:19.527Z
While there are lots of algorithms for special cases of GI (planar, trees, bounded genus, bounded eigenvalue multiplicity, other graph classes), it's not like there are a whole bunch of algorithms for the general case (unlike, say, matching). Marzio De Biasi's comment pretty much sums it up...
Joshua Grochow
CC BY-SA 3.0
2014-12-13T06:58:09.800Z
What research have you done?  We expect you to do a significant amount of research/investigation on your own before asking, and show your research in the question. You're asking for a lot -- a comprehensive of all graph isomorphism algorithms is probably too much to ask others to provide -- so you should demonstrate a comparable amount of effort on your own first, before asking.
D.W.
<graph-theory><graph-isomorphism>
Known algorithms for Graph isomorphism
shuhalo
# Known algorithms for Graph isomorphism

(Asked by: username_0 on 2014-12-12)

What algorithms are known for the graph isomorphism problem? Can those algorithms be related to algorithms for other graph theoretical problems (e.g. subgraph problem, counting graph isomorphisms)?

**Tags:** graph-theory, graph-isomorphism

> **Comments:**
> **username_1**: Your question seems too broad. BTW the fastest known algorithm runs in $e^{O(\sqrt(n \log n))}$ (Babai et al, 1983); there are a bunch of well known softwares for GI that use some (advanced) techniques to prune the search tree: nauty, saucy, bliss, traces, conauto. For an up-to-date comparison/bibliography see [Practical graph isomorphism, II](http://arxiv.org/abs/1301.1493).  
> **username_2**: I think the question is fine, and would be very interested to see a survey answer along the lines of this one: http://cstheory.stackexchange.com/questions/9241/approximation-algorithms-for-metric-tsp/11557#11557 McKay's survey seems more focused on implementation issues, and less on algorithms per say.  
> **username_3**: While there are lots of algorithms for special cases of GI (planar, trees, bounded genus, bounded eigenvalue multiplicity, other graph classes), it's not like there are a whole bunch of algorithms for the general case (unlike, say, matching). username_1's comment pretty much sums it up...  
> **username_4**: What research have you done?  We expect you to do a significant amount of research/investigation on your own before asking, and show your research in the question. You're asking for a lot -- a comprehensive of all graph isomorphism algorithms is probably too much to ask others to provide -- so you should demonstrate a comparable amount of effort on your own first, before asking.  

---

## 0 answers

