Re: (Probably flawed) Polynomial time Graph Isomorphism

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!


I don't understand the modified hash phase.

Suppose G1 and G2 have the same initial hashes.

I pick a node in G1 to modify. Now what do I do? Try modifying each node
in G2 the same way to see if the hashes now match? Then what, if I get
multiple matches?

Patricia
.

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: 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: (Probably flawed) Polynomial time Graph Isomorphism
    ... Bill Cox wrote: ... significant progress analyzing this algorithm. ... Since graph isomorphism is a long studied problem with no known ...
    (comp.theory)
  • 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)