[Nauty] [genrang] Regular graph

Brendan McKay bdm at cs.anu.edu.au
Wed Jun 30 00:49:01 EST 2004


* Sébastien Sorlin <chrome.nickel at wanadoo.fr> [040629 16:45]:
> 2) The degree must be between 0 and 8. I never can use 8, genrang seems to be 
> too long to produce this kind of graph. Is it normal? (0 to 7 is good and 
> fast).

genrang uses a very simple algorithm for generating random regular
graphs that unfortunately takes time proportional to exp( c d^2 )
for degree d, where c is some constant (maybe c=1/4).  This means
it is usable only for low degree.  There are algorithms for larger d
but they are quite complicated and I don't have an implementation.

Brendan.




More information about the Nauty mailing list