Randomly sampling molecules

Authors
Goldberg, LA Jerrum, M
Citation
La. Goldberg et M. Jerrum, Randomly sampling molecules, SIAM J COMP, 29(3), 2000, pp. 834-853
Citations number
26
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
29
Issue
3
Year of publication
2000
Pages
834 - 853
Database
ISI
SICI code
0097-5397(20000112)29:3<834:RSM>2.0.ZU;2-F
Abstract
We give a polynomial-time algorithm for the following problem: Given a degr ee sequence in which each degree is bounded from above by a constant, selec t, uniformly at random, an unlabelled connected multigraph with the given d egree 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.