Subject: Graph Isomorphism Algorithm Summary

From: Shlomi Fish <[email-masked]>
Date: Wed, 6 Dec 2000 14:21:58 +0200 (IST)

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        [email-masked] 
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

The prefix "God Said" has the extraordinary logical property of 
converting any statement that follows it into a true one.

---

From: Omer Musaev <[email-masked]>
Date: Wed, 06 Dec 2000 17:20:59 +0000

> 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.

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.

> 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.