Re: Need Graph Isomorphism Algorithm Debunked
 From: "Bill Cox" <bill@xxxxxxxxxxxxx>
 Date: 9 Oct 2006 12:32:15 0700
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 25node 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 counterexamples, 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 Bside 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 selfcomparisons.
.
 FollowUps:
 Re: Need Graph Isomorphism Algorithm Debunked
 From: Booted Cat
 Re: Need Graph Isomorphism Algorithm Debunked
 References:
 Re: Need Graph Isomorphism Algorithm Debunked
 From: Bill Cox
 Re: Need Graph Isomorphism Algorithm Debunked
 From: Bill Cox
 Re: Need Graph Isomorphism Algorithm Debunked
 From: Bill Cox
 Re: Need Graph Isomorphism Algorithm Debunked
 From: Bill Cox
 Re: Need Graph Isomorphism Algorithm Debunked
 From: Phil Carmody
 Re: Need Graph Isomorphism Algorithm Debunked
 Prev by Date: Re: enc and auth scheme with tiny cryptograms
 Next by Date: Re: How to approach decrypting Ciphertext
 Previous by thread: Re: Need Graph Isomorphism Algorithm Debunked
 Next by thread: Re: Need Graph Isomorphism Algorithm Debunked
 Index(es):
Relevant Pages
