Hostname: page-component-74656f9884-kv2lp Total loading time: 0 Render date: 2026-11-04T16:58:43.273Z Has data issue: false hasContentIssue false
  • English
  • Français

Generating Random Regular Graphs Quickly

Published online by Cambridge University Press:  01 July 1999

A. STEGER  and
N. C. WORMALD
A. STEGER
Affiliation:
Institut für Informatik, Technische Universität München, D-80290 München, Germany (e-mail: steger@informatik.tu-muenchen.de)
N. C. WORMALD
Affiliation:
Department of Mathematics and Statistics, University of Melbourne, Parkville, VIC 3052, Australia (e-mail: nick@ms.unimelb.edu.au)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 → ∞. The expected runtime for these ds is [Oscr](nd2).

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 8 , Issue 4 , July 1999 , pp. 377 - 396
Copyright
1999 Cambridge University Press