Combinatorics, Probability and Computing

Table of Contents - 1999 - Volume 8, Issue 04  


Generating Random Regular Graphs Quickly

A. STEGER a1 and N. C. WORMALD a2 1
a1 Institut für Informatik, Technische Universität München, D-80290 München, Germany (e-mail: steger@informatik.tu-muenchen.de)
a2 Department of Mathematics and Statistics, University of Melbourne, Parkville, VIC 3052, Australia (e-mail: nick@ms.unimelb.edu.au)

Abstract

We present a practical algorithm for generating random regular graphs. For all d growing as a small power of n, the d-regular graphs on n vertices are generated approximately uniformly at random, in the sense that all d-regular graphs on n vertices have in the limit the same probability as n [rightward arrow] [infty infinity]. The expected runtime for these ds is [script O](nd2).

(Received June 3 1998)
(Revised November 11 1998)


Footnotes

1 Research supported by the Australian Research Council.