Fast uniform generation of regular graphs

DOI10.1016/0304-3975(90)90164-DzbMath0694.68044OpenAlexW2087275015MaRDI QIDQ909471

Alistair Sinclair, Mark R. Jerrum

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(90)90164-d

zbMATH Keywords

polynomial time algorithmregular graphsgeneration problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (29)

Moments of Uniform Random Multigraphs with Fixed Degree Sequences ⋮ Improving the characterization of P-stability for applications in network privacy ⋮ Approximating degree sequences with regular graphic sequences (extended abstract) ⋮ Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs ⋮ Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow ⋮ Mixing time of the switch Markov chain and stable degree sequences ⋮ A sequential algorithm for generating random graphs ⋮ On the random generation and counting of matchings in dense graphs ⋮ Fast uniform generation of random graphs with given degree sequences ⋮ Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs ⋮ Approximate sampling of graphs with near-\(P\)-stable degree intervals ⋮ The switch Markov chain for sampling irregular graphs and digraphs ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ Network-Ensemble Comparisons with Stochastic Rewiring and Von Neumann Entropy ⋮ Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs ⋮ Rejection sampling of bipartite graphs with given degree sequence ⋮ Sampling hypergraphs with given degrees ⋮ The mixing time of switch Markov chains: a unified approach ⋮ Configuring Random Graph Models with Fixed Degree Sequences ⋮ On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries ⋮ How likely is an LLD degree sequence to be graphical? ⋮ The random transposition dynamics on random regular graphs and the Gaussian free field ⋮ Random k -noncrossing RNA structures ⋮ Half-graphs, other non-stable degree sequences, and the switch Markov chain ⋮ An Almost m-wise Independent Random Permutation of the Cube ⋮ Asymptotic enumeration by degree sequence of graphs of high degree ⋮ Uniform Generation of Random Regular Graphs ⋮ Uniform generation of spanning regular subgraphs of a dense graph ⋮ Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• Approximate counting, uniform generation and rapidly mixing Markov chains
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Approximating the Permanent
• Uniform generation of random regular graphs of moderate degree
• Generating Random Unlabelled Graphs
• Generating random regular graphs

This page was built for publication: Fast uniform generation of regular graphs