Randomly Sampling Molecules

Leslie Ann Goldberg, Mark Jerrum

Type: Article

Publication Date: 2000-01-01

Citations: 6

DOI: https://doi.org/10.1137/s0097539797318864

Abstract

We give a polynomial-time algorithm for the following problem: Given a degree sequence in which each degree is bounded from above by a constant, select, uniformly at random, an unlabelled connected multigraph with the given degree sequence. We also give a polynomial-time algorithm for the following related problem: Given a molecular formula, select, uniformly at random, a structural isomer having the given formula.

Locations

SIAM Journal on Computing - View
Warwick Research Archive Portal (University of Warwick) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Randomly sampling molecules	1997	Leslie Ann Goldberg Mark Jerrum
+ PDF Chat	Generating graphs randomly	2021	Catherine Greenhill
+	Expand and Contract: Sampling graphs with given degrees and other combinatorial families	2013	James Zhao
+ PDF Chat	Sampling random graphs with specified degree sequences	2024	Upasana Dutta Bailey K. Fosdick Aaron Clauset
+	Generating graphs randomly	2022	Catherine Greenhill
+	Generating Random Networks Without Short Cycles	2008	Mohsen Bayati Andrea Montanari Amin Saberi
+	Generating Random Networks Without Short Cycles	2008	Mohsen Bayati Andrea Montanari Amin Saberi
+ PDF Chat	Generating Random Networks Without Short Cycles	2016	Mohsen Bayati Andrea Montanari Amin Saberi
+	Generating Random Unlabelled Graphs	1987	Nicholas Wormald
+ PDF Chat	Combinatorial Miller–Hagberg Algorithm for Randomization of Dense Networks	2018	Hiroki Sayama
+ PDF Chat	Generating Random Networks Without Short Cycles	2018	Mohsen Bayati Andrea Montanari Amin Saberi
+	Efficient sampling of graphs with arbitrary degree sequence	2010	Charo I. del Genio Hyun-Ju Kim Zolt 'an Toroczkai Kevin E. Bassler
+	Uniformly sampling graphs with self-loops and a given degree sequence.	2017	Joel Nishimura
+	Generating simple directed random graphs with a given degree sequence with a fast algorithm.	2021	Femke van Ieperen Ivan Kryven
+	Sampling of Random Graphs with Prescribed Degree Sequence	2019	Weibin Zhang
+	Random generation of combinatorial structures from a uniform distribution	1986	Mark Jerrum Leslie G. Valiant Vijay V. Vazirani
+	Sampling complete graphs	2009	Luca Giuzzi Anita Pasotti
+	Generating labeled planar graphs uniformly at random	2007	Manuel Bodirsky Clemens Gröpl Mihyun Kang
+ PDF Chat	Generating a Random Sink-free Orientation in Quadratic Time	2002	Henry Cohn Robin Pemantle James Propp
+	Randomly $H$ graphs	1986	Gary Chartrand Ortrud R. Oellermann Sergio Ruiz

Works That Cite This (1)

Action	Title	Year	Authors
+	The Complexity of Ferromagnetic Ising with Local Fields	2006	ESLIE ANN GOLDBERG Mark Jerrum

Works Cited by This (7)

Action	Title	Year	Authors
+	The asymptotic number of labeled graphs with given degree sequences	1978	Edward A. Bender E. Rodney Canfield
+	Generating Random Unlabelled Graphs	1987	Nicholas Wormald
+	The asymptotic connectivity of labelled regular graphs	1981	Nicholas Wormald
+ PDF Chat	Uniform generation of random regular graphs of moderate degree	1990	Brendan D. McKay Nicholas Wormald
+	Fast uniform generation of regular graphs	1990	Mark Jerrum Alistair Sinclair
+	Almost all Regular Graphs are Hamiltonian	1983	Béla Bollobás
+	The Asymptotic Number of Unlabelled Regular Graphs	1982	Béla Bollobás