[Nauty-list] Another Automorphism question...

Brendan McKay bdm at cs.anu.edu.au
Sat Jun 11 13:54:37 EST 2011


No, nauty is not polynomial time in the worst case.  You are correct
that the theoretical question is still open.

Brendan.

* Grant Farmer <xsw1234 at yahoo.com> [110611 13:06]:
> Hi, I was wondering if the automorphism decision algorithm in NAUTY is polynomial time or not.  I am under the impression that finding automorphisms has not been shown to be able to be done in polynomial time, but I do not know about the decision version.
> 
> Grant Farmer
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list




More information about the Nauty mailing list