2

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

shuhalo
  • 1,165
  • 5
  • 13
  • 3
    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. – Marzio De Biasi Dec 12 '14 at 16:21
  • 1
    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 Dec 12 '14 at 18:31
  • 1
    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 Dec 13 '14 at 04:25
  • 1
    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. Dec 13 '14 at 06:58

0 Answers0