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
Mok-Kong Shen (mok-kong.shen@stud.uni-muenchen.de)
Fri, 14 Aug 1998 09:42:10 +0100
bram wrote:
> 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.
The problem of graph isomorphism is not the solubility but to devise
a method that is fast enough for practical cases. Some twenty years
ago I wrote a program for a friend to determine whether a certain
sub-structure is present in some organic molecules. There one has
to match nodes with the same atom. The program worked for the intended
purpose but I don't think it would be practical to run it even today
on graphs having several thousands of nodes.
M. K. Shen
------------------------------------------------------
M. K. Shen, Postfach 340238, D-80099 Muenchen, Germany
+49 (89) 831939 (6:00 GMT)
mok-kong.shen@stud.uni-muenchen.de
http://www.stud.uni-muenchen.de/~mok-kong.shen/
(last updated: 11th August 98. origin site of WEAK1, WEAK2 and WEAK3.)
(containing 2 mathematical problems with rewards totalling US$500)
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58