The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

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 Page
  • Offical site

    Problem Links

      
    Graph Isomorphism (10)
      
    Generating Graphs (7)



    This page last modified on 2008-07-10 .
    www.algorist.com