[Nauty-list] Sparse or dense?

[Brendan McKay]

For random graphs the tipping point comes when the average degree is
about the square root of the number of vertices. 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.

Brendan.

* Hans Georg Schaathun <georg+nauty at schaathun.net> [130414 03:08]:
> Hi,
> 
> I am using nauty for the equivalence of linear codes every now and
> then.  Ten years ago I settled for the dense data structure.  Revisiting
> the problem now, I note that there is a sparse data structure as well.
> 
> Is there any guidance available on when each data structure is optimal?
> Or possibly performance comparisons?  I have tried searching without 
> finding anything.
> 
> In my particular case, I have a bipartite graph with about 50-75
> vertices in one set at a thousand in the other.  The vertices in
> the larger set have degree 15-20.
> 
> Thanks in advance for any pointers or advice,
> -- 
> :-- Hans Georg
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list