5
$\begingroup$

I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would like to compare with the others.

$\endgroup$
1
  • $\begingroup$ Also, I came up with an algorithm for computing chromatic polynomials that has a better running time than that employed by MATLAB's MuPad notebook. This is on account of better average branching of my algorithm. Do you have any suggestions of chromatic polynomial computation algorithms with which I can compare my algorithm? $\endgroup$ Mar 26, 2016 at 21:59

2 Answers 2

8
$\begingroup$

To be taken seriously as a competitor you should be able to perform well on at least some of the difficult graph classes collected by Adolfo Piperno.

$\endgroup$
6
  • $\begingroup$ I believe igraph has C implementation of bliss and vf2, (there is link in the other answer). $\endgroup$
    – joro
    Mar 27, 2016 at 11:11
  • $\begingroup$ Is any of these provably sub-exponential? Not asking if they are significantly faster than sub-exponential almost always. $\endgroup$
    – joro
    Mar 27, 2016 at 11:59
  • 1
    $\begingroup$ @joro: No, they are exponential in the worst case. $\endgroup$ Mar 27, 2016 at 22:47
  • $\begingroup$ I'd also link the paper B. D. McKay, A. Piperno, Practical graph isomorphism, II, Journal of Symbolic Computation, 60, 94-112 (2014) for a recent comparison of these (except VF2, it seems). $\endgroup$ Mar 30, 2016 at 5:41
  • 2
    $\begingroup$ @Victor: Random graphs are too easy. A better way to seek false negatives is to take graphs from Piperno's collection and form two random relabellings of them. $\endgroup$ Apr 17, 2016 at 23:17
3
$\begingroup$

To compare your implementation with others, I would recommend to benchmark it against sage,igraph and McKay's canonical labelling (IIRC part of the nauty package). The last two are optional packages in sage, so probably installing sage (possibly in a virtual machine) is the easiest way.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.