sartin@hplabsz.HPL.HP.COM (Rob Sartin) (11/16/89)
Goal: Generate a random connected graph G, with n nodes, each having degree c. I can't find a way to characterize the graphs to make them easy to generate. I have found a couple of different ways to generate regular graphs that meet the criteria, but this leaves out many possible solutions. Ideas? Rob Sartin internet: sartin@hplabs.hp.com Software Technology Lab uucp : hplabs!sartin Hewlett-Packard voice : (415) 857-7592
bdm659@csc.anu.oz (11/19/89)
In article <4366@hplabsz.HPL.HP.COM>, sartin@hplabsz.HPL.HP.COM (Rob Sartin) writes: > Goal: > > Generate a random connected graph G, with n nodes, each having degree c. > > I can't find a way to characterize the graphs to make them easy to > generate. I have found a couple of different ways to generate regular > graphs that meet the criteria, but this leaves out many possible > solutions. Ideas? > > Rob Sartin internet: sartin@hplabs.hp.com > Software Technology Lab uucp : hplabs!sartin > Hewlett-Packard voice : (415) 857-7592 The best exact algorithm is given in B. D. McKay and N. C. Wormald, Uniform generation of random regular graphs of moderate degree, soon to appear in Journal of Algorithms. This gives an algorithm which has polynomial expected time if c = o(n^(1/3)). If c is bigger than that, you are out of luck: no practical exact algorithm is known, though M. Jerrum and A. Sinclair have an approximation algorithm of untested practical utility [sorry, I don't have the details with me.] The McKay/Wormald algorithm generates labelled regular graphs with exactly uniform distribution. If you only want connected graphs, just throw out the ones that aren't connected. All but a small fraction are connected if c>=3. The version with the best theoretical running time would be too tedious to program, but the simpler version given in the paper should be practical. If you can't wait for the J. Alg. article to appear, ask the second author to send you a copy: Nick Wormald at nick@maths.aukuni.ac.nz. Brendan McKay. bdm@anucsd.oz or bdm@anucsd.oz.au or bdm659@csc1.anu.oz.au