[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