Fast uniform generation of random graphs with given degree sequences

DOI10.1002/rsa.21004zbMath1522.68735arXiv1905.03446OpenAlexW3139020493MaRDI QIDQ6074660

Andrii Arman, Pu Gao, Nicholas C. Wormald

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphsrejection samplingrandomized generation algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Combinatorics. Abstracts from the workshop held January 1--7, 2023

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The asymptotic number of labeled graphs with given degree sequences
• Uniform generation of random regular graphs of moderate degree
• Uniform generation of random graphs with power-law degree sequences
• Generating Random Regular Graphs Quickly
• Uniform Generation of Random Regular Graphs
• The switch Markov chain for sampling irregular graphs (Extended Abstract)
• Sampling Regular Graphs and a Peer-to-Peer Network
• Generating random regular graphs