Uniform Generation of Random Regular Graphs

DOI10.1137/15M1052779zbMath1368.05133arXiv1511.01175MaRDI QIDQ4978195

Pu Gao, Nicholas C. Wormald

Publication date: 18 August 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.01175

zbMATH Keywords

Markov chainregular graphsswitchinguniform generation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Combinatorics. Abstracts from the workshop held January 1--7, 2023, Fast uniform generation of random graphs with given degree sequences, Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs, The average distance and the diameter of dense random regular graphs, Random graphs with given vertex degrees and switchings, Sampling hypergraphs with given degrees, Uniform generation of spanning regular subgraphs of a dense graph, A triangle process on regular graphs, The planted k-factor problem

Cites Work

• A sequential algorithm for generating random graphs
• Fast uniform generation of regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• The asymptotic number of labeled graphs with given degree sequences
• Uniform generation of random regular graphs of moderate degree
• Generating Random Regular Graphs Quickly
• The switch Markov chain for sampling irregular graphs (Extended Abstract)
• Asymptotic Enumeration of Sparse Multigraphs with Given Degrees
• Sampling Regular Graphs and a Peer-to-Peer Network
• Generating random regular graphs
• Generating random regular graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item