[Nauty-list] Sparse or dense?

Brendan McKay bdm at cs.anu.edu.au
Mon Apr 15 23:17:09 EST 2013


Traces is very often faster than nauty.  The more difficult the
graph class, the larger the difference can be.  There are plots
at http://pallini.di.uniroma1.it : follow the "experiments" link.
Again, your graph class is different from those tested so it is
hard to predict.

Brendan.

* Hans Georg Schaathun <georg+nauty at schaathun.net> [130415 20:00]:
> On Sun, Apr 14, 2013 at 08:19:29AM +1000, Brendan McKay wrote:
> > For random graphs the tipping point comes when the average degree is
> > about the square root of the number of vertices.
> 
> Thanks a lot.  That's a very useful point of reference.
> It strongly indicates that I have at least to try the sparse structure.
> 
> >                                                   We didn't run any
> > comparisons for graphs like your highly unbalanced bipartite graphs,
> > so I can't predict which is best. You need to experiment. You can
> > also try Traces, which uses the same graph structure as sparse nauty.
> 
> Is traces algorithmically different from nauty?  I had the impression
> that the difference was in the output only.  I am only interested in 
> the canonical labelling, and I use nauty inside a search to eliminate
> equivalent graphs.  Could traces be faster or slower than sparse nauty
> depending on the input graph?
> 
> -- 
> :-- Hans Georg
> 
> _______________________________________________
> 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