[Nauty-list] Another Automorphism question...
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.
* 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
More information about the Nauty