Re: Need Graph Isomorphism Algorithm De-bunked


Phil Carmody wrote:
"Bill Cox" <bill@xxxxxxxxxxxxx> writes:
Bill Cox wrote:
Bill Cox wrote:
Here's an interesting paper on "strongly regular graphs", which so far,
don't seem too difficult.

http://citeseer.ist.psu.edu/cameron01strongly.html

Quoting from the paper:

"Another role of strongly regular graphs is aa test cases for graph
isomorphism testing algorithms. The global uniformity ensured by the
definition makes it harder to find a cononical labelling, while the
superexpodential number of graphs means that they cannot be processed
as exceptions."

All I can says is: we pass the test.

I ran the code between all 15 25-node graphs on this page:

http://www.maths.gla.ac.uk/~es/25.vertices

It differentiated them all.

I also finished running all 167 64 node strongly regular graphs against
each other. No counter-examples, all were differentiated.

You are checking that it actually detects isomorphisms too, aren't you?
You've not explicitly said so. Else here's an O(1) algorithm which
correctly differentiates all of the examples you've listed so far.

are_isomorphic(M1, M2) = are_identical(M1,M2)

Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.

Yes, I've compared many of them against eachother, though I've done the
randomization by hand until now. I'll try to find time to randomize
them automatically and do full self-comparisons.

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... isomorphism testing algorithms. ... The global uniformity ensured by the ... I also finished running all 167 64 node strongly regular graphs against ... correctly differentiates all of the examples you've listed so far. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... isomorphism testing algorithms. ... I also finished running all 167 64 node strongly regular graphs against ... correctly differentiates all of the examples you've listed so far. ... randomization by hand until now. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Bill Cox wrote: ... Quoting from the paper: ... isomorphism testing algorithms. ... I also finished running all 167 64 node strongly regular graphs against ...
    (sci.crypt)