Uniform Generation of Random Regular Graphs
From MaRDI portal
Publication:4978195
DOI10.1137/15M1052779zbMath1368.05133arXiv1511.01175MaRDI QIDQ4978195
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
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