[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