Sampling Regular Graphs and a Peer-to-Peer Network
From MaRDI portal
Publication:5437233
DOI10.1017/S0963548306007978zbMATH Open1137.05065DBLPjournals/cpc/CooperDG07arXiv1203.6111OpenAlexW2167223378WikidataQ56323873 ScholiaQ56323873MaRDI QIDQ5437233FDOQ5437233
Authors: Colin Cooper, Martin Dyer, Catherine Greenhill 
Publication date: 18 January 2008
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Abstract: In [Combinatorics, Probability and Computing 16 (2007), 557 - 593, Theorem 1] we proved a polynomial-time bound on the mixing rate of the switch chain for sampling d-regular graphs. This corrigendum corrects a technical error in the proof. In order to fix the error, we must multiply the bound on the mixing time by a factor of d^8 .
Full work available at URL: https://arxiv.org/abs/1203.6111
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (including graph drawing) in computer science (68R10)
Cited In (47)
- Sampling Edge Covers in 3-Regular Graphs
- A triangle process on regular graphs
- Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
- Sampling \(k\)-partite graphs with a given degree sequence
- Lifted algorithms for symmetric weighted first-order model sampling
- Connectivity of random regular graphs generated by the pegging algorithm
- Uniform generation of spanning regular subgraphs of a dense graph
- Uniform generation of random regular graphs
- Rejection sampling of bipartite graphs with given degree sequence
- Title not available (Why is that?)
- Regularized modified log-Sobolev inequalities and comparison of Markov chains
- Linear-time uniform generation of random sparse contingency tables with specified marginals
- Configuring random graph models with fixed degree sequences
- The mixing time of switch Markov chains: a unified approach
- A survey of discrete methods in (algebraic) statistics for networks
- New classes of degree sequences with fast mixing swap Markov chain sampling
- Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
- Expansion and flooding in dynamic random networks with node churn
- A sequential algorithm for generating random graphs
- Sampling regular graphs and a peer-to-peer network
- Approximate sampling of graphs with near-\(P\)-stable degree intervals
- Mixing time of the swap Markov chain and \(P\)-stability
- Half-graphs, other non-stable degree sequences, and the switch Markov chain
- Exact sampling of graphs with prescribed degree correlations
- A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
- Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
- Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
- Mixing time of the switch Markov chain and stable degree sequences
- Approximate sampling and counting of graphs with near-regular degree intervals
- Constructing and sampling directed graphs with given degree sequences
- On the bias of traceroute sampling
- Fast uniform generation of random graphs with given degree sequences
- Scalable Uniform Graph Sampling by Local Computation
- Expansion properties of a random regular graph after random vertex deletions
- Sampling contingency tables
- Uniform sampling of digraphs with a fixed degree sequence
- The contact process over a dynamical \(d\)-regular graph
- On the bias of traceroute sampling
- Pegging graphs yields a small diameter
- The switch Markov chain for sampling irregular graphs and digraphs
- Rapid mixing of the switch Markov chain for 2-class joint degree matrices
- The flip Markov chain and a randomising P2P protocol
- Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence
- Fast sequential creation of random realizations of degree sequences
- Sampling hypergraphs with given degrees
- How to determine if a random graph with a fixed degree sequence has a giant component
- The flip Markov chain for connected regular graphs
This page was built for publication: Sampling Regular Graphs and a Peer-to-Peer Network
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5437233)
