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
Mike Stay (staym@accessdata.com)
Wed, 12 Aug 1998 10:51:49 -0600
Is anyone familiar with NAUTY (No AUTomorphisms, Yes?)? It's the best
known test for graph isomorphisms, and I was wondering what order of
magnitude a graph would have to be to make the test infeasible. A graph
with 864 vertices and only one automorphism only took 10 minutes to test
with NAUTY
(http://www.cs.sfu.ca/cs/people/GradStudents/khopkins/personal/papers/graph_isomorphism/node12.html)
Apparently even finding hard graphs is non-trivial. Are there any
implementations of zero-knowledge proofs based on the graph isomorphism
problem I could try NAUTY on?
-- Mike Stay Cryptographer / Programmer AccessData Corp. mailto:staym@accessdata.com
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58