[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