On 2014-03-03, Volker Braun <vbraun.n...@gmail.com> wrote: > AFAIK both implement the same basic algorithm. My guess is that nauty > quickly realizes that it has a huge problem and starts constructing graph > invariants in an attempt to answer it to the negative. If you were to > compare two graphs that are actually isomorphic I'm pretty sure that you > wouldn't find such a big difference. For practical applications it is of > course important to have this trick using easily-accessible graph > invariants, but its probably not that hard to implement..
it's known that most "easy" graph invariants, such as counting sizes of isomorphism classes of k-vertex subgraphs on each arc, are only heuristics (cf. Cai-Furer-Immerman results). However, if you average over sufficiently large classes of graphs, these heuristics appear to work quite well. -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/groups/opt_out.
