A linear-time algorithm for sampling graphs with given degrees

MaRDI QIDQ2789573zbMATH OpenFDO

Authors James Y. Zhao

Publication date 1 March 2016

Full work available at URL https://hal.inria.fr/hal-01077251v2/document

zbMATH Keywords

graphs with given degreesMarkov chain couplingperfect matchinguniform sampling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Monte Carlo methods (65C05) Analysis of algorithms (68W40)

Recommendations

• Fast uniform generation of random graphs with given degree sequences
• Uniform generation of random regular graphs
• A sequential algorithm for generating random graphs
• A Sequential Algorithm for Generating Random Graphs
• Fast uniform generation of regular graphs

Cited in

(8)

• Sampling hypergraphs with given degrees
• Uniform random sampling of planar graphs in linear time
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• Randomly Sampling Molecules
• On the Complexity of Sampling Vertices Uniformly from a Graph
• Constructing and sampling directed graphs with given degree sequences
• Exact sampling of graphs with prescribed degree correlations
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs

This page was built for publication: A linear-time algorithm for sampling graphs with given degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789573)