NAUTY -- Graph Isomorphism
The world's fastest isomorphism testing program is Nauty, by
Brendan D. McKay.
Nauty (No AUTomorphisms, Yes?) is a set of very efficient C language
procedures for
determining the automorphism group of a vertex-colored graph.
It provides this information
in the form of a set of generators, the size of group,
and the orbits of the group.
Nauty is also able to produce a canonically-labeled isomorph of the graph,
to assist in isomorphism testing.
It was the basis of the first program to generate all
the 11-vertex graphs without isomorphs, and can test most graphs of
less than 100 vertices in well under a second.
Nauty has been successfully ported to a variety of operating systems and
C compilers.
It may be obtained from
http://cs.anu.edu.au/people/bdm/.
It is free for educational and research applications, but for
commercial use contact the author at bdm@cs.anu.edu.au.
Download Files (local site)Brendan McKay's PageOffical site
Problem Links
This page last modified on 2008-07-10
.
www.algorist.com
