[Nauty-list] Hard Instances
Ramon Bejar Torres
ramon at diei.udl.cat
Thu Mar 22 04:20:36 EST 2007
One particular very hard case is the
graph associated with a latin square, that
is a strongly regular graph, that is
asymmetric (it has only the trivial automorphism),
but is very hard for Nauty to find
Greg Tener wrote:
> I have three questions about hard instances for nauty (they're so few
> and hard to find).
> I have found most of the planes at
> http://www.uwyo.edu/moorhouse/pub/planes27/ to be difficult, some are
> easier with using invariants such as cellfano and cellfano2.
> Hadamard equivalence of Hadamard matrices are mentioned in the new
> users guide as well as a citing of a paper that describes a family
> requiring exponential growth of the number of nodes.
> So, which Hadamard matrices in particular are hard? I've found some at
> Neil Sloane's site.
> Also, are there any graphs with trivial automorphism group known to be
> hard for nauty?
> Are there any other notable graphs which take a long time?
> University of Central Florida
> -Greg Tener-
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
More information about the Nauty