Sampling Regular Graphs and a Peer-to-Peer Network
From MaRDI portal
Publication:5437233
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 .
Recommendations
Cited in
(47)- Linear-time uniform generation of random sparse contingency tables with specified marginals
- Mixing time of the swap Markov chain and \(P\)-stability
- Half-graphs, other non-stable degree sequences, and the switch Markov chain
- Approximate sampling and counting of graphs with near-regular degree intervals
- Constructing and sampling directed graphs with given degree sequences
- Sampling Edge Covers in 3-Regular Graphs
- Uniform generation of random regular graphs
- Sampling \(k\)-partite graphs with a given degree sequence
- A survey of discrete methods in (algebraic) statistics for networks
- On the bias of traceroute sampling
- Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence
- Connectivity of random regular graphs generated by the pegging algorithm
- Fast sequential creation of random realizations of degree sequences
- Configuring random graph models with fixed degree sequences
- Fast uniform generation of random graphs with given degree sequences
- Regularized modified log-Sobolev inequalities and comparison of Markov chains
- Sampling contingency tables
- A triangle process on regular graphs
- How to determine if a random graph with a fixed degree sequence has a giant component
- Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
- Sampling hypergraphs with given degrees
- Pegging graphs yields a small diameter
- New classes of degree sequences with fast mixing swap Markov chain sampling
- A sequential algorithm for generating random graphs
- The flip Markov chain for connected regular graphs
- A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
- On the bias of traceroute sampling
- Scalable Uniform Graph Sampling by Local Computation
- Uniform sampling of digraphs with a fixed degree sequence
- The mixing time of switch Markov chains: a unified approach
- Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
- Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
- The flip Markov chain and a randomising P2P protocol
- Rapid mixing of the switch Markov chain for 2-class joint degree matrices
- Lifted algorithms for symmetric weighted first-order model sampling
- Rejection sampling of bipartite graphs with given degree sequence
- Sampling regular graphs and a peer-to-peer network
- Uniform generation of spanning regular subgraphs of a dense graph
- Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
- Exact sampling of graphs with prescribed degree correlations
- scientific article; zbMATH DE number 1743766 (Why is no real title available?)
- The switch Markov chain for sampling irregular graphs and digraphs
- The contact process over a dynamical \(d\)-regular graph
- Approximate sampling of graphs with near-\(P\)-stable degree intervals
- Expansion and flooding in dynamic random networks with node churn
- Mixing time of the switch Markov chain and stable degree sequences
- Expansion properties of a random regular graph after random vertex deletions
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)
