Loading ...
Sorry, an error occurred while loading the content.

Graph Isomorphism Algorithm Summary

Expand Messages
  • Shlomi Fish
    Well, I have spoken with Prof. Shimon Even and described the final version of the algorithm to him. He said that such an algorithm, up to some minor
    Message 1 of 2 , Dec 6, 2000
    • 0 Attachment
      Well, I have spoken with Prof. Shimon Even and described the final version
      of the algorithm to him. He said that such an algorithm, up to some minor
      differences, was suggested by Guttlib and Corneal about 30 years ago.

      In that article they claimed that it has polynomial time, but Corneal
      later corrected himself and published an article which said that for some
      graphs it was actually O(V^k*V!). Still, for most real-life graphs it
      works nicely.

      Prof. Even also told me of an algorithm by a certain Eugene Luks, which
      for link multiplicites lesser than 5 or so, has a polynomial time. This
      algorithm is based on some concepts as G&C's but also on Set Theory and
      other mathematical fields.

      If I have the time and nerve I might package the code and put it on CPAN.
      But don't count on it.

      So, it's nice that I came by it by myself (even though it's based on
      Moore's reduction for finite automata which I learned about in "Digital
      Systems"), but it's not a new thing.

      Regards,

      Shlomi Fish



      ----------------------------------------------------------------------
      Shlomi Fish shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      The prefix "God Said" has the extraordinary logical property of
      converting any statement that follows it into a true one.
    • Omer Musaev
      ... Well, that s the life. But anyway, your work was impressive, and even if it will not make as an algorithm, it surely did show you many interesting aspects
      Message 2 of 2 , Dec 6, 2000
      • 0 Attachment
        Shlomi Fish wrote:

        > Well, I have spoken with Prof. Shimon Even and described the final version
        > of the algorithm to him. He said that such an algorithm, up to some minor
        > differences, was suggested by Guttlib and Corneal about 30 years ago.
        >

        Well, that's the life. But anyway, your work was impressive, and even if
        it will not make
        as an algorithm, it surely did show you many interesting aspects of
        graph theory.

        > If I have the time and nerve I might package the code and put it on CPAN.
        > But don't count on it.

        What you have already done is there, and in case someone will need it, I
        suppose your code may
        be transformed into something both useful and applicable.

        > So, it's nice that I came by it by myself (even though it's based on
        > Moore's reduction for finite automata which I learned about in "Digital
        > Systems"), but it's not a new thing.

        Again, there is a lot of things that we come up to and then discover
        that we are late by some
        50 years. However, I think that thinking is a joyful experience and that
        even if you do not
        wind up with a "product", your efforts were not pointless.


        > Regards,
        >
        > Shlomi Fish
        >
      Your message has been successfully submitted and would be delivered to recipients shortly.