Re: (Probably flawed) Polynomial time Graph Isomorphism

OK. I suggest you also post your experimental algorithm to sci.math and
sci.math.research since it seems there are more serious researchers
there. You could also search for and contact serious computer
scientists such as D.E. Knuth. Also search the literature for relevant
papers. This Google result page has some things that look interesting:

http://www.google.com/search?sourceid=mozclient&ie=utf-8&oe=utf-8&q=%22Graph+Isomorphism%22+Polynomial


Bill Cox wrote:
Hey, Bytecool. Glad to see you keep yourself busy reading Usenet
news. Actually, I use to post frequently back in the late 80-s, and
early 90-s, then I lost access. It's nice to have Google providing it!

I'm a bit zorched today, so I doubt I'll make more progress. However,
I think I'll probably be able to find a counter-example that shows this
hash-based labeling of nodes isn't enough to differentiate asymmetric
nodes. I'm upgrading the code to look for such cases...

There's an equivalent thread in sci.crypt where a couple guys have made
significant progress analyzing this algorithm. It's at:

http://groups.google.com/group/sci.crypt/browse_thread/thread/079227a49dd64623/229f2580fa487470#229f2580fa487470

yaoziyuan@xxxxxxxxx wrote:
Hey Bill, nice to see you here... I'm the BTSlave-likeminded guy on
your Yahoo Messenger... It seems to be your first series of posts on
the Usenet :O


Bill Cox wrote:
I've written a graph isomorphism program that determines if two graphs
are isomorphic. It runs in O(N^3).

Since graph isomorphism is a long studied problem with (AFAIK) no known
polynomial time solution, my algorithm is more than likely flawed. Any
help finding the flaws would be appreciated! The web site is

http://www.billrocks.org/ideas

Thanks!

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Since graph isomorphism is a long studied problem with (AFAIK) no known ... my algorithm is more than likely flawed. ... this is a randomized algorithm that has a probability of failing (that is, ...
    (sci.crypt)
  • Re: Algorithm to determine matrix similarity
    ... such an S would be an algorithm to decide whether ... The OP's problem subsumes the graph isomorphism ... 2-colored undirected graphs (with self-edges). ... matrices amounts to classifying the nodes by ...
    (sci.math)
  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... Glad to see you keep yourself busy reading Usenet ... significant progress analyzing this algorithm. ... Since graph isomorphism is a long studied problem with no known ... my algorithm is more than likely flawed. ...
    (comp.theory)
  • Re: Is graph isomorphism in P?
    ... to do the sorts of things that have been stated ... "Is graph isomorphism in P?"... ... whether the algorithm works or not. ...
    (sci.math)
  • Re: Combinatorics of binary operations
    ... binary operations on a set with cardinality n. ... Any such algorithm would give, as a special case, an algorithm for ... graph isomorphism. ...
    (sci.math)