Uniform Parallel Generation of Combinatorial Structures
-------------------------------------------------------
Michele Zito, Ida Pu and Alan Gibbons
Department of Computer Science, University of Warwick
We describe an RNC algorithm for the uniform generation of
unlabelled undirected graphs with a specified number of nodes.
The algorithm is archetypal in the sense that many other RNC
algorithms for the uniform generation of other combinatorial
structures are possible using the same framework. The framework
is based upon a parallisation of a result of Dixon and Wilf and
uses simple probabilistic analysis to convert the expected
running time of a sequential algorithm into a worst case
parallel running time.