Sampling Regular Graphs and a Peer-to-Peer Network

DOI10.1017/S0963548306007978zbMath1137.05065arXiv1203.6111OpenAlexW2167223378WikidataQ56323873 ScholiaQ56323873MaRDI QIDQ5437233

Colin Cooper, Martin Dyer, Catherine Greenhill

Publication date: 18 January 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

regular graphspeer-to-peer network

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items

Sampling Edge Covers in 3-Regular Graphs ⋮ Mixing time of the switch Markov chain and stable degree sequences ⋮ A sequential algorithm for generating random graphs ⋮ Expansion and flooding in dynamic random networks with node churn ⋮ Fast uniform generation of random graphs with given degree sequences ⋮ Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs ⋮ Unnamed Item ⋮ Approximate sampling of graphs with near-\(P\)-stable degree intervals ⋮ Unnamed Item ⋮ The switch Markov chain for sampling irregular graphs and digraphs ⋮ Sampling contingency tables ⋮ A survey of discrete methods in (algebraic) statistics for networks ⋮ Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs ⋮ The flip Markov chain for connected regular graphs ⋮ Expansion properties of a random regular graph after random vertex deletions ⋮ Constructing and sampling directed graphs with given degree sequences ⋮ Rejection sampling of bipartite graphs with given degree sequence ⋮ Sampling hypergraphs with given degrees ⋮ Exact sampling of graphs with prescribed degree correlations ⋮ The mixing time of switch Markov chains: a unified approach ⋮ Configuring Random Graph Models with Fixed Degree Sequences ⋮ New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling ⋮ How to determine if a random graph with a fixed degree sequence has a giant component ⋮ Uniform Sampling of Digraphs with a Fixed Degree Sequence ⋮ Connectivity of random regular graphs generated by the pegging algorithm ⋮ Half-graphs, other non-stable degree sequences, and the switch Markov chain ⋮ Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings ⋮ Uniform Generation of Random Regular Graphs ⋮ Sampling \(k\)-partite graphs with a given degree sequence ⋮ A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix ⋮ Uniform generation of spanning regular subgraphs of a dense graph ⋮ Fast Sequential Creation of Random Realizations of Degree Sequences ⋮ Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices ⋮ A triangle process on regular graphs