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!

Flaw is described at your last sentence of proof, It's hard construct
graphs with same hashes but it's not impossible. It could be one graoh
from lot but that matter

.

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)