Re: Need Graph Isomorphism Algorithm De-bunked

Bill Cox wrote:
OK, sorry for my misinterpretation. I've waxed optimistic again, and
I think there may even be a chance for my misinterpreted version.
In any event, I think that the fixed number of iterations of your
steps 3 and 4 above may be replaced by the criterion that the nodes'
values become stagnant.

--Mike Amling

You're proof for graphs of 8 or fewer nodes is very cool. Here's a
recent algorithm and proof that claim graph isomorphism is polynomial
in time:

http://arxiv.org/abs/math.CO/0202085
http://arxiv.org/abs/math.CO/0607770

I haven't yet taken the time to understand "K-orbits" of graphs, or
"combinational algebraics", or any of the group-theory jargon.
However, it does make me optimistic that a hashing-based algorithm
works.

What's an orbit? Is it like a cycle in permutations?

--Mike Amling
.