Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58
bram (bram@gawth.com)
Thu, 13 Aug 1998 17:28:26 -0700 (PDT)
On Wed, 12 Aug 1998, Mike Stay wrote:
> Apparently even finding hard graphs is non-trivial.
And coming up with algorithms for finding isomorphisms is very easy. As
long as a graph doesn't have any automorphisms, any algorithm which gives
a unique value which for each node which doesn't change with permutation
will find isomorphisms easily (and I think the automorphism problem can be
fixed easily too.)
A reasonably straightforward way of calculating such a value is the
following:
For a node x, compute how many ways there are of getting to each other
node in exactly n steps, where n = the total number of nodes. Sort that
list, and the result is a value for x which is the same regardless of the
initial permutation (applying a secure hash to it results in a much more
manageable and equally useful value, of course.)
That technique requires the use of a big number class, and isn't
horrendously fast (it's n^3 for each node, n^4 for the whole thing), but
it's still polynomial, and for it not to work would require very, very
purposeful construction of the graph.
I personally would just throw in the towel beforehand and view finding
hard graph isomorphism problems as a lost cause.
-Bram
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58