Sampling Regular Graphs and a Peer-to-Peer Network

Colin Cooper, Martin Dyer, Catherine Greenhill

Type: Article

Publication Date: 2006-08-29

Citations: 136

DOI: https://doi.org/10.1017/s0963548306007978

View Publication

Locations

Combinatorics Probability Computing - View

Similar Works

Action	Title	Year	Authors
+	Sampling regular graphs and a peer-to-peer network	2005	Colin Cooper Martin Dyer Catherine Greenhill
+	Corrigendum: Sampling regular graphs and a peer-to-peer network	2012	Colin Cooper Martin J.S. Dyer Catherine Greenhill
+	Corrigendum: Sampling regular graphs and a peer-to-peer network	2012	Colin Cooper Martin Dyer Catherine Greenhill
+	The switch Markov chain for sampling irregular graphs	2014	Catherine Greenhill
+	The switch Markov chain for sampling irregular graphs and digraphs	2017	Catherine Greenhill Matteo Sfragara
+	The switch Markov chain for sampling irregular graphs and digraphs	2017	Catherine Greenhill Matteo Sfragara
+	The switch Markov chain for sampling irregular graphs and digraphs	2017	Catherine Greenhill Matteo Sfragara
+	The switch Markov chain for sampling irregular graphs: extended abstract	2015	Catherine Greenhill
+	The switch Markov chain for sampling irregular graphs (Extended Abstract)	2014	Catherine Greenhill
+	A note on parallel sampling in Markov graphs	2019	Verena Bauer Karl Fürlinger Göran Kauermann
+	A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs	2011	Catherine Greenhill
+	A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs	2011	Catherine Greenhill
+ PDF Chat	A Polynomial Bound on the Mixing Time of a Markov Chain for Sampling Regular Directed Graphs	2011	Catherine Greenhill
+	A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks	2006	Tomás Feder Adam Guetz Milena Mihail Amin Saberi
+ PDF Chat	Towards Random Uniform Sampling of Bipartite Graphs with given Degree Sequence	2013	István Miklós Péter L. Erdős Lajos Soukup
+	The birthday problem and Markov chain Monte Carlo	2007	Itaı Benjamini Ben Morris
+ PDF Chat	Uniform Data Sampling from a Peer-to-Peer Network	2007	Souptik Datta Hillol Kargupta
+	Connectedness of the Degree Bounded Star Process	2003	Catherine Greenhill ANDRZEJ RUCISKI Nicholas Wormald
+	Towards random uniform sampling of bipartite graphs with given degree sequence	2010	Péter L. Erdős Istán Miklós Lajos Soukup
+	Towards random uniform sampling of bipartite graphs with given degree sequence	2010	Péter L. Erdős Istán Miklós Lajos Soukup

Works That Cite This (107)

Action	Title	Year	Authors
+ PDF Chat	Sampling hypergraphs with given degrees	2021	Martin Dyer Catherine Greenhill Pieter Kleer James Ross Leen Stougie
+	Lifted Algorithms for Symmetric Weighted First-Order Model Sampling	2023	Yuanhong Wang Juhua Pu Yuyi Wang Ondřej Kuželka
+ PDF Chat	Lifted algorithms for symmetric weighted first-order model sampling	2024	Yuanhong Wang Juhua Pu Yuyi Wang Ondřej Kuželka
+	Towards random uniform sampling of bipartite graphs with given degree sequence	2010	Péter L. Erdős Istán Miklós Lajos Soukup
+	A non-P-stable class of degree sequences for which the swap Markov chain is rapidly mixing.	2019	Péter L. Erdős Ervin Györi Tamás Róbert Mezei István Miklós Dániel Soltész
+	Mixing time of the swap Markov chain and P-stability	2019	Péter L. Erdős Catherine Greenhill Tamás Róbert Mezei István Miklós Dániel Soltész Lajos Soukup
+ PDF Chat	New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling	2017	Péter L. Erdős István Miklós Zoltán Toroczkai
+	The mixing time of the swap (switch) Markov chains: a unified approach.	2019	Péter L. Erdős Catherine Greenhill Tamás Róbert Mezei István Miklós Dániel Soltész Lajos Soukup
+	The switch Markov chain for sampling irregular graphs: extended abstract	2015	Catherine Greenhill
+	Uniform generation of spanning regular subgraphs of a dense graph	2018	Pu Gao Catherine Greenhill

Works Cited by This (12)

Action	Title	Year	Authors
+	Simple Markov-chain algorithms for generating bipartite graphs and tournaments	1999	Ravi Kannan Prasad Tetali Santosh Vempala
+	The asymptotic number of labeled graphs with given degree sequences	1978	Edward A. Bender E. Rodney Canfield
+ PDF Chat	Correlations in two-dimensional vortex liquids	1994	Jun Hu A. H. MacDonald Brendan D. McKay
+ PDF Chat	Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains	2004	Mark Jerrum Jung-Bae Son Prasad Tetali Eric Vigoda
+	Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow	1992	Alistair Sinclair
+ PDF Chat	Uniform generation of random regular graphs of moderate degree	1990	Brendan D. McKay Nicholas Wormald
+	Generating Random Regular Graphs Quickly	1999	Angelika Steger N. C. Wormald
+	Fast uniform generation of regular graphs	1990	Mark Jerrum Alistair Sinclair
+	A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs	1980	Béla Bollobás
+	Almost all regular graphs are hamiltonian	1994	Robert W. Robinson N. C. Wormald